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

다익스트라 알고리즘을 활용하여 풀 수 있는 문제이다.

테스트 케이스 1번을 예시로 설명해보겠다.

1. 시작 좌표로부터의 최단 거리를 저장하기 위한 2차원 배열을 별도로 생성하고, 배열의 값을 모두 INF로 초기화한다.

(INF는 아직 도달하지 못한 좌표를 의미하며 1e9로 값을 할당하였다.)

2. 최소 힙을 생성하여, 시작좌표(0,0)의 도둑 루피 값을 정렬 기준으로 최소힙에 삽입한다.

3. 최소 힙에서 가장 도둑 루피가 작은 값을 팝하여, 상하좌우 좌표를 검사한다.

아직 최소힙에 들어있는 값은 시작 좌표말고 없으므로, 시작 좌표의 값이 뽑힌다.

배열의 범위를 벗어나지 않으면서 현재 위치에서의 최단 비용과 이동할 위치의 최단 비용을 합친 값이, 기존 distance 배열에서의 값보다 작아진다면(우리는 최소 비용을 갖고 목적지에 도달하는것이 목표이므로) distance의 값을 갱신하고,

갱신한 값과 좌표를 최소 힙에 삽입한다.

4. 최소 힙에서 가장 도둑 루피가 작은 값을 팝하여, 상하좌우 좌표를 검사한다.

최소 힙에서 가장 비용이 적은 값은 8이므로, 8(1,0)이 뽑힌다.

(1,0) 좌표의 인접한 좌표 (0,0),(2,1),(1,1)은 누적 비용 8에 각각의 좌표에서의 도둑 루피 값을 더하면 13, 11, 17 이 되므로, (2,0), (1,1) 좌표의 distance배열의 값을 갱신하고 최소 힙에 삽입한다.

5. 최소 힙에서 가장 도둑 루피가 작은 값을 팝하여, 상하좌우 좌표를 검사한다.

최소 힙에서 가장 비용이 적은 값은 10이므로, 10(0,1)이 뽑힌다.

(0,1) 좌표의 인접한 좌표 (0,0),(0,2),(1,1)은 누적 비용 10에 각각의 좌표에서의 도둑 루피 값을 더하면 15,14,19 가 되므로,

(0,2) 좌표의 distance배열의 값을 갱신하고 최소 힙에 삽입한다.

6. 최소 힙에서 가장 도둑 루피가 작은 값을 팝하여, 상하좌우 좌표를 검사한다.

최소 힙에서 가장 비용이 적은 값은 11이므로, 11(2,0)이 뽑힌다.

(2,0) 좌표의 인접한 좌표 (1,0),(2,1)은 누적 비용 11에 각각의 좌표에서의 도둑 루피 값을 더하면 19,13이 되므로,

(2,1) 좌표의 distance배열의 값을 갱신하고 최소 힙에 삽입한다.

7.  최소 힙에서 가장 도둑 루피가 작은 값을 팝하여, 상하좌우 좌표를 검사한다.

최소 힙에서 가장 비용이 적은 값은 13이므로, 13(2,1)이 뽑힌다.

(2,1) 좌표의 인접한 좌표 (1,1),(2,2)은 누적 비용 13에 각각의 좌표에서의 도둑 루피 값을 더하면 22,20이 되므로,

(2,2) 좌표의 distance배열의 값을 갱신하고 최소 힙에 삽입한다.

목적지인 (2,2)에 도달하였으므로, 탐색을 종료하고 distance[n-1][n-1]값을 정답으로 출력한다.

위 아이디어를 코드로 옮기면 아래와 같다.

import heapq
INF = int(1e9)  # 무한 거리
t = 1  # 현재 몇번째 문제인지 기록
dx = [0, 0, -1, 1]
dy = [-1, 1, 0, 0]


def dijkstera():
    global distance
    queue = []  # 최소 힙으로 사용하기 위한 배열
    # 시작 좌표에서의 가격, 시작 좌표를 최소 힙에 삽입
    heapq.heappush(queue, (graph[0][0], 0, 0))
    while queue:
        dist, x, y = heapq.heappop(queue)  # 가장 코스트가 적은 노드 뽑기
        # 네 가지 방향에 대해서
        for i in range(4):
            nx = x + dx[i]
            ny = y + dy[i]
            # 범위를 벗어나지 않으면서
            if 0 <= nx < n and 0 <= ny < n:
                # 현재 점을 거쳐서 가면 더 짧아진다면 갱신
                if dist + graph[nx][ny] < distance[nx][ny]:
                    distance[nx][ny] = dist + graph[nx][ny]
                    # 최소힙에 푸쉬
                    heapq.heappush(queue, (distance[nx][ny], nx, ny))
                # 목적지에 도달하였다면
                if (nx, ny) == (n-1, n-1):
                    return


while True:  # 0이 입력될때까지 반복
    n = int(input())
    if n == 0:
        break
    graph = [list(map(int, input().split())) for _ in range(n)]
    # 각 좌표에 대한 최단 경로를 저장하기 위한 배열 생성
    distance = [[INF]*n for _ in range(n)]
    # 다익스트라 알고리즘 수행
    dijkstera()
    # 정답 출력
    print(f"Problem {t}:", distance[n-1][n-1])
    t += 1