[백준-파이썬] 4485: 초록 옷 입은 애가 젤다지?

문제 보러 가기!

ㅎㅎ제목부터 재밌다. (TMI: 나도 젤다의 전설 바람의 숨결! 게임을 종종 한다 ㅎㅎ )
전에 나는 평범한 다익스트라 문제만 풀어봤는데, 조금 응용한 문제를 풀어봐서 재밌었다.

시작하는 점이 정해져 있고(제일 왼쪽 위), 음의 간선이 없으니까 다익스트라가 가능하다.
다익스트라는 특정 노드에서 시작해서, 다른 노드로 가는 최단 경로를 각각 구해준다. 이 문제는 잃은 도둑 루피가 최소로 되도록! 0,0 점에서 N-1,N-1까지 이동해야 한다.

조금 주의할 것이 있다고 하면~

1. 1차원 리스트로 최단 경로 테이블을 만들기 위해서, i좌표와 j 좌표를 곱해서 만든 하나의 숫자로 인덱스 위치를 표현했다.
2. 상하좌우로 갈 때도 그 하나의 숫자를 바꿔줘야 한다. (위: -N, 아래: N, 왼쪽: -1, 오른쪽:1)
3. 옆으로 못 가는 경우를(맨 왼쪽이거나 맨 오른쪽) 따로 체크해 줘야 한다..!! (아래 코드 참고)

다익스트라 어떻게 짜는지 몰라서, 좀 보면서 짰는데..
자다 깨서도 짤 수 있게 익숙하게.. 많이 연습해야겠당

import heapq
import sys

input = sys.stdin.readline
MIIS = lambda: map(int, input().strip().split())

INF = 125 * 125 * 9 + 1

tc = 0
while True:
    N = int(input())
    if N == 0:  # 종료
        break

    tc += 1
    cave = []

    for i in range(N):
        tmp = list(MIIS())
        cave.extend(tmp)

    # 다익스트라
    distance = [INF] * (N * N)
    q = []

    # 출발점
    heapq.heappush(q, (cave[0], 0))  # 비용, 위치
    distance[0] = cave[0]

    while q:
        dist, now = heapq.heappop(q)  # 젤 잃는 도둑 루피 적은 지점까지의 비용, 위치
        # 이미 처리되었으면 패스
        if distance[now] < dist:
            continue

        # 그 지점에서 연결된 다른 지점들 비용 업데이트 (상하좌우)
        for k in (-N, N, -1, 1):
            # 옆으로 못 가는 경우..
            if now % N == 0 and k == -1:  # 왼쪽 못가(왼쪽 끝)
                continue
            if (now + 1) % N == 0 and k == 1:  # 오른쪽 못 가(오른쪽 끝)
                continue

            tmp = now + k

            if 0 <= tmp < N * N:  # 범위 확인
                cost = dist + cave[tmp]  # 그 지점 들를 때 비용
                if cost < distance[tmp]:
                    distance[tmp] = cost
                    heapq.heappush(q, (cost, tmp))

    print(f'Problem {tc}: {distance[-1]}')