[백준] 2665번 미로만들기 - 파이썬/다익스트라

https://www.acmicpc.net/problem/2665

import heapq

n = int(input())

graph = [ list(map(int,input())) for _ in range(n) ]

for i in range(n):
    for j in range(n):
        if graph[i][j]==0:
            graph[i][j]=1
        else:
            graph[i][j]=0


INF = int(1e9)

distance = [ [INF]*(n) for _ in range(n) ]
distance[0][0]=0
dx = [1,-1,0,0]
dy = [0,0,1,-1]

q = []

def dij():

    heapq.heappush(q, (graph[0][0], 0, 0))

    while q:

        dist, now_x, now_y = heapq.heappop(q)

        if now_x == n-1 and now_y == n-1:
            break

        for i in range(4):

            next_x = now_x+dx[i]
            next_y = now_y+dy[i]

            if 0<=next_x<n and 0<=next_y<n:

                cost = dist + graph[next_x][next_y]

                if cost<distance[next_x][next_y]:
                    distance[next_x][next_y] = cost
                    heapq.heappush(q,(cost,next_x,next_y))

dij()

print(distance[n-1][n-1])

백준 1261번 문제와 같은 유형의 문제이다.

벽을 뚫는 2차원 배열 다익스트라 문제인데 이러한 문제는 다음과 같이 접근한다.

1. 통로를 0, 벽을 1로 하는 그래프를 만든다.
2. 시작점에서 끝점까지 최소 가중치를 구한다.

만약 벽에 막히지 않았다면 최소 가중치가 0일 것이고, 최소 가중치가 1이 나왔다면 1개의 벽만 뚫어도 연결되었다는 뜻이다.