2차원 다익스트라 문제 두번째!

BOJ 2158 - 산악자전거 링크
(2022.10.17 기준 G4)
(치팅하면 엄복동이 혼냄)

문제

R행 C열의 행렬로 표현되는 산이 있고, 산악자전거를 타고 초기 속도가 V, 높이 차이에 의해 속도가 가속이나 감속된다고 하면, (1, 1) 위치에서 (R, C) 위치로 이동할 때의 필요한 최소 시간

알고리즘

각 칸마다 가중치를 변화시키는 요소가 있고, 이 가중치에 따른 시간을 최소로 하여 목적지에 도달해야 하므로 다익스트라

풀이

전에 풀이를 올렸던 4485번 문제와 같은 유형인 2차원 다익스트라다.
동일하게 distance 배열을 2차원으로 만들고 상하좌우로 움직이면서 거리를 갱신해나가면 된다.

좀 헷갈릴만한 요소는 속도.
문제에서 속도가 V라는 의미는 단위시간동안 V칸을 움직일 수 있다는 의미라고 명시되어 있다.
이는 역으로 말하면, 속도가 V이면 1칸 움직이는 데에 (1 / V) 시간이 걸린다는 뜻이다.
그러므로 다익스트라를 돌릴 때, 힙에는 걸리는 시간(거리), 위치 그리고 현재 속도를 넣고,
현재 거리 + (1 / 현재 속도)와 다음 위치의 거리를 비교하면 된다. 다음 속도는 문제에 명시되어 있듯이 현재 속도에 (2 ** (현재 높이 - 다음 높이))를 곱해주면 된다.

코드

import sys; input = sys.stdin.readline
import heapq
from math import inf

def solve():
    V, R, C = map(int, input().split()) # 초기 속도, 행의 수, 열의 수
    matrix = [list(map(int, input().split())) for _ in range(R)] # 산의 모습

    # 2차원 다익스트라
    # 각 칸마다 제일 빠르게 도착하는 시간을 저장하면서 진행
    distance = [[inf] * C for _ in range(R)]
    queue = [[0, 0, 0, V]] # 거리, 위치 r, c, 속도
    distance[0][0] = 0

    # 다익스트라 시작
    while queue:
        d, r, c, v = heapq.heappop(queue)
        # 저장된 시간보다 지금 걸리는 시간이 더 크다면
        # 지금 걸리는 시간으로 갱신할 필요가 없음
        if distance[r][c] < d:
            continue
        for rr, cc in [(r - 1, c), (r + 1, c), (r, c - 1), (r, c + 1)]: # 상하좌우
            # 다음 위치가 범위 안이며, 그 위치에 저장된 시간보다 지금 시간 + 한칸 움직이는데 걸리는 시간이 더 작으면 갱신
            if 0 <= rr < R and 0 <= cc < C and distance[rr][cc] > distance[r][c] + 1 / v:
                distance[rr][cc] = distance[r][c] + 1 / v
                heapq.heappush(queue, [distance[rr][cc], rr, cc, v * 2 ** (matrix[r][c] - matrix[rr][cc])])
    print(distance[R - 1][C - 1])

solve()

여담

조금 있으면 단풍 구경하러 가는 시기가 된다. 날씨도 눈 깜빡할 새에 쌀쌀해지고.. 시간 참 빠르다 허허