[골드4] 1261번 : 알고스팟

🛠 문제

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

👩🏻‍💻 해결 방법

2665번 : 미로만들기와 유사한 문제이다
BFS만으로도 해결할 수 있는 문제이지만, 우선순위큐(최소힙)를 활용하여 문제를 해결했다


소스 코드

from heapq import heappush, heappop
m, n = map(int, input().split())
dx = [1, -1, 0, 0]
dy = [0, 0, -1, 1]
graph = []
visit = [[0] * m for i in range(n)]
for i in range(n):
    graph.append(list(map(int, input())))
    
def dijkstra():
    heap = []
    heappush(heap, [0, 0, 0])
    visit[0][0] = 1
    while heap:
        cnt, x, y = heappop(heap)
        if x == n - 1 and y == m - 1:
            print(cnt)
            return
        for i in range(4):
            nx = x + dx[i]
            ny = y + dy[i]
            if 0 <= nx < n and 0 <= ny < m and visit[nx][ny] == 0:
                heappush(heap, [cnt + 1 if graph[nx][ny] == 1 else cnt, nx, ny])
                visit[nx][ny] = 1
dijkstra()