BOJ - 1261

백준 문제 링크
알고스팟

❓접근법

1. 다익스트라 알고리즘을 활용했다.
2. 초기값 INF = int(1e9),
   미로의 상태를 graph,
   상,하,좌,우로 움직이기 때문에 dx, dy 지정,
   x, y는 0으로 지정한다.( 출발점 )
3. 거리를 나타낼 2차원 리스트 distance,
   q = [[graph[x][y], x, y]],
   distance[x][y] = graph[x][y]로 지정한다.
4. while q 동안 다익스트라 알고리즘으로
   4 방향을 돌면서 distance를 갱신한다.
5. 마지막으로 distance[n-1][m-1]의 값을 출력하면 끝!

👌🏻코드

import heapq

INF = int(1e9)

m, n = map(int, input().split())

graph = []

for _ in range(n):
    graph.append(list(map(int, input())))
    
dx = [0, 0, 1, -1]
dy = [1, -1, 0, 0]

x, y = 0, 0

distance = [[INF] * m for _ in range(n)]

q = [[graph[x][y], x, y]]
distance[x][y] = graph[x][y]

while q:
    
    dist, x, y = heapq.heappop(q)
    
    if distance[x][y] < dist:
        continue
        
    for d in range(4):
        nx = x + dx[d]
        ny = y + dy[d]
        
        if nx < 0 or nx >= n or ny < 0 or ny >= m:
            continue
            
        cost = dist + graph[nx][ny]
        
        if cost < distance[nx][ny]:
            distance[nx][ny] = cost
            heapq.heappush(q, (cost, nx, ny))
            
print(distance[n-1][m-1])