[BOJ/백준] 1261 알고스팟

import heapq
import sys
input = sys.stdin.readline
N,M = map(int,input().split())

arr = [list(map(int,list(input().strip()))) for _ in range(M)]

node_list = []
heapq.heappush(node_list,(0,0,0))
INF = float('inf')
dp = [[INF]*N for _ in range(M)]
dx = [-1,1,0,0]
dy = [0,0,1,-1]
dp[0][0] = 0
while node_list:
    dis,x,y = heapq.heappop(node_list)
    for i in range(4):
        nx = x + dx[i]
        ny = y + dy[i]
        if 0<=nx<M and 0<=ny<N:
            if dp[nx][ny] > dp[x][y] + arr[nx][ny]:
                dp[nx][ny] = dp[x][y] + arr[nx][ny]
                heapq.heappush(node_list,(dp[nx][ny],nx,ny))

print(dp[M-1][N-1])

 

BFS를 이용해서 푸는 방법도 있을것 같은데, 다익스트라로 풀었다. 기본적으로 하는 BFS와 동일하다. 대신 2차원으로 바뀌었기 때문에, 4방향을 탐색하면, 현재 dp값이 줄어드는 경우에만 heapq에 push를 해주고, 여기서는 거리대신 해당 arr에 있는 벽의 유무로 판별해주었다.