[Python] 녹색 옷 입은 애가 젤다지? - 백준 (최단경로)

해당 글은 백준 4485번 '녹색 옷 입은 애가 젤다지?' 문제를 다룬다.

문제

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

4485번: 녹색 옷 입은 애가 젤다지?

 

설명

(0, 0)에서 (n-1, n-1)까지 이동할 때 최소 비용으로 가야하므로 최단 경로를 구하는 알고리즘 중 다익스트라를 활용하면 된다.
이때 주의할 점은 heapq를 사용하므로 heappush할 때 비용이 먼저 위치하도록 한다!
 

코드

import heapq

dx = [-1, 1, 0, 0]
dy = [0, 0, -1, 1]
INF = int(1e9)

def dijkstra():
    distance = [[INF]*n for _ in range(n)]
    distance[0][0] = arr[0][0]
    q = []
    heapq.heappush(q, (arr[0][0], 0, 0))
    while q:
        dist, x, y = heapq.heappop(q)
        if distance[x][y] < dist:
            continue
        for i in range(4):
            nx = x + dx[i]
            ny = y + dy[i]
            if nx >= 0 and nx < n and ny >= 0 and ny < n:
                cost = dist + arr[nx][ny]
                if cost < distance[nx][ny]:
                    distance[nx][ny] = cost
                    heapq.heappush(q, (cost, nx, ny))
    return distance[n-1][n-1]

t = 1
while True:
    n = int(input())
    if n == 0:
        break
    arr = []
    for i in range(n):
        arr.append(list(map(int, input().split())))
    result = dijkstra()
    print(f'Problem {t}: {result}')
    t += 1