[백준/파이썬] #17836

오랜만에 답을 안 보고 30분 안에 풀었다. BFS와 heap을 사용해서 풀었다. 

import heapq

INF = 1e9

dx = [-1, 1, 0, 0]
dy = [0, 0, -1, 1]

def direct_path(end_x, end_y):
    start_x, start_y = 0, 0
    visited = [[False] * M for _ in range(N)]
    visited[start_x][start_y] = True
    heap = []
    heapq.heappush(heap, (0, start_x, start_y))
    while heap:
        dist, cur_x, cur_y = heapq.heappop(heap)
        if cur_x == end_x and cur_y == end_y:
            return dist
        
        for k in range(4):
            nx, ny = cur_x + dx[k], cur_y + dy[k]
            if nx < 0 or nx >= N or ny < 0 or ny >= M:
                continue
            if not visited[nx][ny] and graph[nx][ny] != 1:
                heapq.heappush(heap, (dist+1, nx, ny))
                visited[nx][ny] = True

    return INF


if __name__ == "__main__":
    N, M, T = map(int, input().split())
    graph = []
    gram_x, gram_y = 0, 0
    for i in range(N):
        lst = list(map(int, input().split()))
        graph.append(lst)
        if 2 in lst:
            gram_x, gram_y = i, lst.index(2)

    dist_princess = direct_path(N-1, M-1)
    dist_gram = direct_path(gram_x, gram_y)
    gram_to_princess = (N-1-gram_x) + (M-1-gram_y)

    if dist_princess == INF and dist_gram == INF:
        print("Fail")
    else:
        answer = min(dist_princess, dist_gram + gram_to_princess)
        if answer <= T:
            print(answer)
        else:
            print("Fail")