[백준/Python] 녹색 옷 입은 애가 젤다지?

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

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

import sys, heapq

# 동서남북
dx = [0, 0, -1, 1]
dy = [1, -1, 0, 0]
count = 1 # 순서

def dijkstra():
    queue = []
    heapq.heappush(queue, (graph[0][0], 0, 0)) # 시작 노드 큐에 삽입
    dist[0][0] = graph[0][0]

    while queue:
        cur_dist, x, y = heapq.heappop(queue) # 현재 노드 비용, x값, y값
        if cur_dist > dist[x][y]: # 현재 노드 비용이 더 크다면 넘어감
            continue
        for i in range(4): # 동서남북 노드 확인
            xi = x + dx[i]
            yi = y + dy[i]
            if 0 <= xi < n and 0 <= yi < n: # 범위 내에 있다면
                cost = cur_dist + graph[xi][yi] # 비용 계산
                if cost < dist[xi][yi]: # 비용이 dist값보다 작으면
                    heapq.heappush(queue, (cost, xi, yi)) # 해당 노드 큐에 삽입
                    dist[xi][yi] = cost # 비용 수정

while True:
    n = int(input())
    if n == 0:
        break

    graph = [list(map(int, input().split())) for _ in range(n)]
    dist = [[sys.maxsize] * n for _ in range(n)]

    dijkstra()
    print(f'Problem {count}: {dist[n-1][n-1]}')
    count += 1

1. 필요한 정보를 입력받고 필요한 변수를 생성한다.

2. 다익스트라를 수행한다.

     2-1. 우선순위 큐를 생성하고 시작노드의 비용은 graph[0][0]으로 만든다. 큐에 시작 노드를 삽입하는데 꼭 (비용, x위치, y위치) 순으로 넣어야 한다.

     2-2. 큐에 값이 없을 때까지 다음을 반복한다.

     2-3. 큐에서 현재 노드를 가져온다. 현재 노드의 비용이 dist 값보다 크면 비교할 것도 없으므로 넘어간다.

     2-4. 그렇지 않다면 현재 노드와 동서남북으로 연결된 노드를 가져온다. 연결된 노드의 비용를 계산하고 그 비용이 dist의 값보다 작다면 큐에 삽입한 후 비용을 수정한다.

3. 결과를 출력한다.