백준 2665 : 미로만들기 (Python)

본문 링크

import sys,heapq
input=sys.stdin.readline

dx=[0,0,-1,1]
dy=[-1,1,0,0]
def Dijkstra():

    dp[0][0]=0
    heap=[] ; heapq.heappush(heap,(0,0,0))

    while heap:

        value,x,y=heapq.heappop(heap)

        if dp[x][y]<value:
            continue

        for i in range(4):
            nx=x+dx[i] ; ny=y+dy[i]
            if 0<=nx<N and 0<=ny<N:

                if value+graph[nx][ny]<dp[nx][ny]:

                    dp[nx][ny]=value+graph[nx][ny]

                    heapq.heappush(heap,(value+graph[nx][ny] , nx , ny))

    return dp[N-1][N-1]
INF=int(1e9)

N=int(input())
graph=[ list(map(int,input().rstrip())) for _ in range(N) ]
for i in range(N):
    for j in range(N):
        if graph[i][j]:
            graph[i][j]=0
        else:
            graph[i][j]=1
dp=[ [INF]*(N+1) for _ in range(N+1) ]

print(Dijkstra())

📌 어떻게 접근할 것인가?

다익스트라를 이용해 문제를 풀었습니다.
문제에서 이동가능한 노드의 번호가 1 이기 때문에 0 으로 바꿔준 후에 0 인지점을 우선적으로 탐색해줍니다.

다익스트라를 통해서 $(1,1)$ 부터 $(N,N)$ 까지 최단경로를 구할 수 있습니다.