[백준] 24042번 - 횡단보도 (파이썬)

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

 

# 횡단보도
import heapq
import sys
input = sys.stdin.readline
N, M = map(int, input().split())
arr = [[] for _ in range(N+1)]
for i in range(M):
    a, b = map(int, input().split())
    arr[a].append((i, b))
    arr[b].append((i, a))


def dijkstra():
    q = []
    heapq.heappush(q, (0, 1))
    visited = [sys.maxsize for _ in range(N+1)]
    visited[1] = 0
    while q:
        time, node = heapq.heappop(q)
        if node == N:
            return time
        if visited[node] < time:
            continue
        for i, nnode in arr[node]:
            ntime = i+((time-i)//M)*M if (time-i)%M==0 else i+((time-i)//M+1)*M
            if visited[nnode] > ntime+1:
                visited[nnode] = ntime+1
                heapq.heappush(q, (ntime+1, nnode))


print(dijkstra())

 

최단거리, 다익스트라
1. 입력을 받는다. (arr : 횡단보도의 정보 i번째 횡단보도는 a와 b를 연결, 양방향)
2. 다익스트라
    - 1에서 시작, 초기 비용 0
    - node에 존재하는 횡단보도들의 i를 이용해서 ntime을 설정
    - 횡단보도를 거너는데 필요한 시간은 1
    - 따라서 ntime+1이 더 작으면 초기화, push
    - node가 N이면 time 리턴
3. 결괏값 출력

 

Good Bye, BOJ 2021! 문제에 출시된 나름 따끈따끈한 최신 문제이다.

 

횡단보도의 불이 켜지는 시간은 수학식을 이용하자

while문을 이용해서 time보다 ntime이 커질 때까지 M을 무수히 더해주면 시간 초과

 

아래 <2>에서 나온 n-1을 <1>의 식에 대입을 하면

time보다 큰 수들 중 가장 작은 수(해당 횡단보도가 켜지는 시간)를 구할 수 있다.

<1>
i번째 횡단보도의 불이 켜지는 시간들은 등차수열을 이룬다.
i, i+M, i+2M, i+3M ...
이를 식으로 정리하면 i+(n-1)*M 이다.

<2>
횡단보도에 불이 켜지는 시간은 항상 현재 시간 이상이어야 한다.
time <= i+(n-1)*M
(time-i)/M <= n-1

따라서 n-1은 
 - time-i가 M으로 나누어 떨어지면 (time-i)//M
 - 아니면 (time-i)//M+1 이 된다.

몫을 구하는 연산자와 나누기 연산자 주의