녹색 옷 입은 애가 젤다지?

기본 다익스트라문제의 2차원 버전이다.

다익스트라 개념이 익숙하지 않다면 다익스트라 - 중량제한부터 풀어보며 개념을 익히도록 하자.

칸에 적힌 숫자만큼 돈을 잃는다. 이때, 잃는 돈을 최소화 하며 [n-1,n-1] 까지 이동해야 한다. 이는 각 칸에 적힌 숫자가 거리 정보이고, [0,0]노드 부터 [n-1,n-1]까지 최단거리를 구하는 문제와 같다고 볼 수 있다. 예제 입력의 첫번째 케이스를 살펴보자.

3
5 5 4
3 9 1
3 2 7

Crepe

다익스트라를 위한 주어진 리스트와 크기가 동일한 2차원 배열을 만든다. 초기에 모든 칸들은 inf(파이썬에서의 정수 최대값)이다. [0,0]Node에서 시작함으로 dp[0][0]=MAP[0][0]이다.

  • [0,1]Node까지는 10만큼을 잃고, [1,0]Node까지는 8만큼을 잃는다. 이 값들은 모두 기존에 저장되어 있던 값보다 작음으로, dp값을 갱신해준다.

  • 현제 (노란색으로 표시된)방문한 Node를 제외하고 가장 작은 숫자를 가진 칸은 [1,0]Node이다.
  • [1,0]Node에서 갈 수 있는 아직 방문하지 않은 점은 [1,1]Node와 [2,0]Node이다.
  • [1,1]Node까지는 17만큼을 잃고, [2,0]Node까지는 11만큼을 잃는다. 두 값 모두 기존의 값보다 작음으로, dp값을 갱신해준다.

위의 과정을 오른쪽 아래칸에 도달할 때 까지 계속 반복한다.

CODE

import heapq as hq
from collections import deque
import sys
read = sys.stdin.readline

inf = sys.maxsize
dx = [1, 0, 0, -1]
dy = [0, 1, -1, 0]
#Problem 번호 count
i = 0

while True:
    i += 1
    n = int(read())
    if n == 0:
        break
    MAP = list(list(map(int, read().split())) for _ in range(n))
    dp = list(list(inf for _ in range(n)) for _ in range(n))
    dp[0][0] = MAP[0][0]
    #방문하지 않은 점들 중 최소값을 가진 칸을 계속 방문해야한다. >> 최소힙 사용
    heap = [[MAP[0][0], 0, 0]]
    hq.heapify(heap)

    while heap:
        price, a, b = hq.heappop(heap)
        #오른쪽 아래 점에 도달한 경우 그 값을 출력하고 다음 Problem으로 넘어간다.
        if a == n-1 and b == n-1:
            print('Problem ', i, ': ', price, sep="")
        for x, y in zip(dx, dy):
            ax, by = a+x, b+y
            #dp에 이미 저장되어있는 값보다 작을때만 방문한다.
            if 0 <= ax < n and 0 <= by < n and price+MAP[ax][by] < dp[ax][by]:
                dp[ax][by] = price+MAP[ax][by]
                hq.heappush(heap, [dp[ax][by], ax, by])


틀린 부분이 있을 수 있습니다. 피드백 주시면 고치도록 하겠습니다! 감사합니다.👍

[꼭 다시 풀어보기]