[BOJ 24042] 백준 24042번 - 횡단보도

		Good Bye, BOJ 2021! 풀이
A		[BOJ 24039] 2021은 무엇이 특별할까?
B		[BOJ 24040] 예쁜 케이크
C		[BOJ 24041] 성싶당 밀키트
D		[BOJ 24042] 횡단보도

1. 문제

$24042$. 횡단보도 (Good Bye, BOJ 2021! D번)

백준 24042번 - 횡단보도 (https://www.acmicpc.net/problem/24042)

2. 풀이

여러 개의 양방향 경로가 존재하는 그래프이고, $1$번 노드에서 $N(N\leq 100,000)$번 노드로 가는 최소 시간을 구하는 문제이다. 따라서 Dijkstra(다익스트라)를 생각할 수 있다.

주기와 간선 방문 순서를 무시하고 보았을 때, $1+i(0\leq i\lt M)$번째 줄에 나오는 $a$에서 $b$로 가는 횡단보도는 $1+i$분에 이용이 가능하다. 이는 $a-b$ 간선이 $1+i$의 가중치를 갖고 있다고 생각하면 된다.

$2$분에 사용가능한 횡단보도와 $4$분에 사용가능한 횡단보도 두 개를 이용한다면, 총 걸리는 시간은 $4$분이다. 따라서 여러 개의 간선을 지나가면 그 간선들 중 가장 가중치가 큰 값이 총 걸리는 시간이 된다.

시간은 역행 불가능한 요소이기 때문에 가중치 $4$의 간선 다음에 가중치 $2$의 간선을 이용할 수 없다. 이때 주기를 이용한다. 가중치 $2$의 간선은 $2,$ $ 2+M,$ $ 2+2\times M,$ $ 2+3\times M…$의 가중치를 전부 가지고 있다고 볼 수 있다.

따라서 이전 소요 시간보다 지금 이용하는 시간 값이 크거나 같아질 때까지 $M$을 여러 번 더하여 값을 생성하고, 이를 지금 이용하는 시간으로 간주하면 된다. (코드 32~36줄)

예를 들어 현재 소요 시간이 $14$, 지금 이용하려는 횡단보도의 이용시간은 $3$, 주기 $M=5$라면, 지금 이용하려는 횡단보도는 $3,$ $ 3+5=8,$ $ 3+5\times 2=13,$ $ 3+5\times 3=18…$분에 이용 가능하다. 따라서 $14$보다 크거나 같은 값을 가져야 하기 때문에 $18$분에 해당 횡단보도를 이용하면 된다.

3. 채점 결과

4. 회고

.

5. 코드