[백준] 4485번: 녹색 옷 입은 애가 젤다지?

문제

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

풀이

다익스트라를 이용한 풀이
현재 위치에서 이동할 수 있는 상하좌우 공간을 탐색후 다음 거리를 구하고 이 거리와
0,0 부터 각 좌표로 가는 최단 경로가 저장된 distances 배열의 값과 비교한다.

만약 다음 거리가 더 작다면 distances 배열의 값을 재할당한다.
최종적으로 나온 distances 배열에서 목적지 좌표에 저장된 값을 출력한다.

import sys
import heapq

INF = int(1e9)


def dijkstra(y, x, graph):
    N = len(graph[0])
    distances = [[INF] * N for _ in range(N)]
    distances[0][0] = graph[0][0]

    heap = [(graph[0][0], 0, 0)]
    dy = [-1, 1, 0, 0]
    dx = [0, 0, -1, 1]

    while heap:
        cur_distance, cur_y, cur_x = heapq.heappop(heap)
        if cur_distance > distances[cur_y][cur_x]:
            continue

        for i in range(4):
            ny = cur_y + dy[i]
            nx = cur_x + dx[i]
            if 0 <= ny < N and 0 <= nx < N:
                next_distance = cur_distance + graph[ny][nx]

                if next_distance < distances[ny][nx]:
                    distances[ny][nx] = next_distance
                    heapq.heappush(heap, (next_distance, ny, nx))

    return distances


def solution():
    count = 1
    while True:
        N = int(sys.stdin.readline())
        if N == 0:
            break

        graph = []
        for _ in range(N):
            graph.append(list(map(int, sys.stdin.readline().split(" "))))
        distances = dijkstra(0, 0, graph)
        print(f'Problem {count}: {distances[N-1][N-1]}')
        count += 1
    return

solution()