[알고리즘] 미로 만들기

포인트

• 미로를 만드는 만드는 방법? 벽을 몇개를 부수고 들어가야 하는 가? 를 묻는 문제 입니다. 저는 이를 다익스트라 알고리즘 (이진 힙) 을 적용하여 해결하였습니다. 
• 다익스트라 알고리즘은 시간 복잡도 O(E + VlogV) 가집니다.

🧶문서는 항상 수정될 수 있습니다. 비판은 환영합니다. 

python

import heapq

n = int(input())

data = [list(input()) for _ in range(n)]

q = []
distance = [[987654321] * n for _ in range(n)]
distance[0][0] = 0
q.append((0, 0, 0))

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

while q:
    cost, x, y = heapq.heappop(q)
    for i in range(4):
        nx = x + dx[i]
        ny = y + dy[i]

        if not (0 <= nx < n and 0 <= ny < n):
            continue

        if data[nx][ny] == '1' and distance[nx][ny] > cost:
            distance[nx][ny] = distance[x][y]
            q.append((distance[nx][ny], nx, ny))

        if data[nx][ny] == '0' and distance[nx][ny] > cost + 1:
            distance[nx][ny] = distance[x][y] + 1
            heapq.heappush(q, (distance[nx][ny], nx, ny))

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