[BOJ][🟡4][백준#02158] 산악자전거

문제 출처

BAEKJOON Online Judge #2158

문제

다해는 평소 산악자전거 타기를 즐긴다. 다해는 오랜 시간동안 운동을 하는 것도 좋아하지만, 때로는 되도록 짧은 시간동안 산악자전거 타기를 마치기를 원하기도 한다. 산의 모습은 R(1 ≤ R ≤ 100)행 C(1 ≤ C ≤ 100)열의 행렬로 표현된다. 행렬의 각 수는 그 위치의 높이(고도)를 나타낸다. 다해는 현재 행렬의 (1, 1) 위치에 있고, (R, C) 위치로 이동하려 한다. 다해의 (1, 1)위치에서의 초기 속도는 V(1 ≤ V ≤ 1,000,000)이다. 행렬에서의 움직임은 위, 아래, 왼쪽, 오른쪽의 네 방향으로만 가능하다고 하자. 속도가 V라는 의미는 단위시간동안 V칸을 움직일 수 있다는 의미이다. 자전거를 타고 이동하다보면 높이 차이에 의해 속도가 가속되기도 하고 감속되기도 한다. 현재 위치의 높이가 A이고, 이동하려는 위치의 높이가 B일 때, 속도는 배가 된다(2A-B 배). 실제로는 이동하는 도중에 속도가 변하게 되지만, 문제의 편의를 위해서 이동을 완전히 마친 후에 속도가 변하는 것으로 생각하자. 즉, 이동을 할 때에는 처음의 속도를 가지고 이동하는 것으로 한다. 산의 높이에 대한 정보와 초기 속도가 주어졌을 때, (1, 1)의 위치에서 (R, C)의 위치로 이동할 때 필요한 최소 시간을 구해내는 프로그램을 작성하시오.

입력

첫째 줄에 세 정수 V, R, C가 주어진다. 다음 R개의 줄에는 C개의 정수로 행렬이 주어진다. 행렬의 각 수는 -25 이상 25 이하의 정수이다.

출력

첫째 줄에 이동에 필요한 최소 시간을 출력한다. 절대/상대 오차는 10-2까지 허용한다.

예제

입력

1 2 3
2 1 2
9 9 1

출력

2.50

My Sol

import sys
input = sys.stdin.readline
from collections import deque

V, I, J = map(int, input().split())
mat = [list(map(int, input().split())) for _ in range(I)]
time = [[float('inf')]*J for _ in range(I)]
time[0][0] = 0

Q = deque()
Q.append((0, 0, V))
while Q:
    ni, nj, speed = Q.popleft()
    for di, dj in ((-1,0),(1,0),(0,1),(0,-1)):
        si, sj = ni+di, nj+dj
        if not (0<=si<I and 0<=sj<J): continue
        if time[si][sj] <= time[ni][nj] + (1/speed): continue
        time[si][sj] = time[ni][nj] + (1/speed)
        speed_new = speed * (2**(mat[ni][nj]-mat[si][sj]))
        Q.append((si, sj, speed_new))

print(f'{time[I-1][J-1]:.2f}')

deque를 이용해 사방의 time을 확인하고, 만약 해당 좌표까지 도달하는 최단 시간을 갱신할 수 있다면 이를 갱신하고 계산된 기준점과 속도를 Q에 넣어 새로운 기준점으로 삼는다.

결과

맞았습니다!!

모범답안

출처

from heapq import heappush, heappop

v, r, c = map(int, input().split())
li = [list(map(int, input().split())) for _ in range(r)]

dx = [-1, 1, 0, 0]
dy = [0, 0, -1, 1]

heap = []
heappush(heap, (0, 0, 0, v)) # time_spent, x, y, velocity
time_spents = [[float('inf')] * c for _ in range(r)]
time_spents[0][0] = 0

while heap:
    time_spent, x, y, velocity = heappop(heap)
    
    for i in range(4):
        nx = x + dx[i]
        ny = y + dy[i]
        
        if nx < 0 or nx >= r or ny < 0 or ny >= c:
            continue
        n_time_spent = time_spent + 1 / velocity
        if n_time_spent < time_spents[nx][ny]:
            time_spents[nx][ny] = n_time_spent
            nvelocity = velocity * (2 ** (li[x][y] - li[nx][ny]))
            heappush(heap, (n_time_spent, nx, ny, nvelocity))
            
print(time_spents[-1][-1])

거의 10배에 가깝게 연산시간이 짧은 풀이가 있어서 가져와 분석해보려 한다. 방식은 나처럼 time에 대한 2차원 배열에 inf를 넣어 갱신하는 방식이다. 나랑 다른 것은 나는 deque를 사용하고, 이 분은 heap을 사용했다는 것인데, visit 체크를 하는 것도 아닌데 왜 이렇게 연산시간 차이가 나는지 알 수가 없다.

heap의 정렬은 최소 시간을 기준으로 정렬되는데, time 배열을 따로 만들어 체크해주는 부분도 비슷한데, 왜 시간이 이렇게 차이가 날까. 어쩌면 if문을 통과하지 않아 제곱 연산이나 heap에 들어가는 수의 차이가 나서일 것 같다.