23.06.02 - 23.06.03 공부 (그래프 파트2 : 데이크스트라)

이번 파트는 [데이크스트라 알고리즘]이다. 역시 바킹독 문제집을 이용했다. 이전에 풀어놓은 게 좀 있어서 저번 [플로이드 알고리즘] 때보다 문제 수는 적지만, 난이도 분포는 살짝 더 높다.

https://www.acmicpc.net/workbook/view/10433

24042, 1854, 5719, 13907, 22870 해결

 

 

1. 백준 1854번 - K번째 최단경로 찾기

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

1854번: K번째 최단경로 찾기

사실 이 문제의 접근은 예전부터 알고 있었다. 한창 USACO 문제들 밀 적에 Roadblocks(백준 6197번 - https://www.acmicpc.net/problem/6197)를 풀었었는데, 그 때 해답을 참고하면서 알게 되었다.  K=2일 때의 최단 경로를 구하는 문제로, 이 문제의 서브태스크급 문제라고 할 수 있겠다. 먼저 고민해보고 오면 좋다.

각 정점마다 최단 거리를 하나만 저장하는 것이 아니라 최대 $K$개까지를 저장할 수 있도록 변형한다. 만약 어떤 정점의 최단 거리가 이미 $K$개 들어있는 상태에서 또다시 거리를 갱신할 필요가 있을 때엔 어떻게 해야 할까? 새로운 거리가, 이미 있는 거리 목록의 최댓값보다 작다면 이미 있는 거리 목록의 최댓값을 빼고 새로운 거리를 집어넣으면 된다. 이때 이 최댓값을 빠르게 구하기 위해서, 최단 거리 목록 자체를 우선순위큐로 관리하는 것이 좋다.

priority_queue<int> dist[N]

2. 백준 24042번 - 횡단보도

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

24042번: 횡단보도

Good Bye, BOJ 2022를 준비하면서 풀 때에는 죽어도 풀리지 않던 문제가, 이번에 풀 때에는 약간의 고민만으로 풀리게 되었다. 물론 [데이크스트라]라는 태그를 알고 있어서 어렵지 않게 풀린 것이겠지만.. 아무튼..

어떤 지역 $u$, $v$에 대하여 그 지역을 잇는 횡단보도에 현재 시각 $t$일 때 초록불이 켜졌다고 하자. $v$까지의 최단 시간은 $u$까지의 최단 시간에 1을 더한 것임을 알 수 있다. 그런데 현재 시각 $t$에 아직 초록불이 안 켜졌다면 최단 시간은 어떻게 구해야 할까? 주기가 정해져 있으므로 $t$를 $M$으로 나눈 나머지값과 횡단보도에 초록불이 켜지는 시각을 비교하면 된다.

예를 들어, $u$까지의 최단 시간이 11분, 주기 $M$이 5, $u$와 $v$를 잇는 횡단보도는 $kM+3$분마다 초록불이 켜진다고 하자. 11%5의 값이 1, 초록불 켜지는 시각이 3이므로 2분 뒤에 초록불이 켜짐을 알 수 있다. (그리고 건너게 되면 총 3분이 지나게 된다.) 이는 $t%M$에서 초록불 시각을 뺀 것으로 구할 수 있다.

반대로 초록불 켜지는 시각이 더 작은 값이면 어떻게 구해야 할까? 주기 $M$에서  $t%M$과 초록불 시각의 차를 빼는 식을 세워 구할 수 있다. $u$까지의 최단 시간이 14분, 주기 $M$이 5, $u$와 $v$를 잇는 횡단보도는 $kM+3$분마다 초록불이 켜진다고 하자. 14%5의 값이 4, 초록불 켜지는 시각이 3이므로 5-(4-3)=4분 뒤에 초록불이 켜짐을 알 수 있다.

정리하면, 다음 초록불이 켜지는 시각은

1. $i-t\%M$분 후
2. $M - (t\%M-i)$분 후

로 구할 수 있다.

3. 백준 13907번 - 세금

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

13907번: 세금

세금이 $p$만큼 오를 때, 도로 $r$개를 지나는 경로는 세금이 $rp$만큼 오른다는 것을 알 수 있다. 따라서 도로 개수에 대한 각각의 최소 비용 경로를 알고 있어야 하므로, 데이크스트라를 돌릴 때, 지금 몇 개의 도로를 지났는지 또한 우선순위큐에 넣어서 도로 개수당 최단 경로를 모두 갱신해주어야 한다.

최단 경로 상 가질 수 있는 최대 도로의 개수는 $N-1$개이므로, $N-1$개까지의 최단 경로를 모두 구하면 된다.

구한 뒤, 최소 통행료는 나이브하게 구현해도 시간 내에 들어온다.(최대 30001×1000)

4. 백준 5719번 - 거의 최단 경로(원. Almost Shortest Path)

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

5719번: 거의 최단 경로

데이크스트라를 진행한 뒤, 최단 경로를 찾았으면 최단 경로에 이용된 도로를 지운다. 이는 dfs를 이용한 데이크스트라 역추적으로 구할 수 있는데, 문제는 최단 경로가 한 개가 아닐 수도 있다는 점이다. 모든 최단 경로를 지우기 위해서 역추적에 사용할 자료구조로 vector를 이용한다.

re[i]를, i번 노드가 최단 경로를 가질 수 있게 한 바로 전 노드의 집합이라고 하자. 현재 노드 cur에서 다음 노드 nxt를 잇는 간선을 통해 nxt의 최단 거리가 갱신되었다고 하면, re[i]를 우선 모두 비우고 cur을 삽입한다. 만약 nxt의 최단 거리와 동일하다면, re[i]는 비우지 않은 채 cur만 추가한다. 이때는 최단 거리가 이전과 동일한 상태이므로 우선순위큐에 넣지 않아야 한다.

마지막 $D$번 노드부터 dfs를 통해 re[]를 역추적해나간다. 이때 하나의 간선이 여러 번 호출될 수 있으므로 방문 체크 또한 해주어야 한다.(이 부분 때문에 시간 초과가 났다..) 역추적된 간선들은 사용하지 않도록 체크한 뒤 데이크스트라를 다시 한 번 돌리면 답이 도출된다.

5. 백준 22870번 - 산책 (large)

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

22870번: 산책 (large)

[거의 최단 경로] 문제가 간선을 지우는 문제였다면, 이 문제는 정점을 지우는 문제. 이 때문에 난이더는 조금 더 쉽다.

눈여겨봐야 할 부분은 처음 $S$에서 $E$로 갈 때 최단 경로가 사전순으로 제일 앞에 오는 경로여야 한다는 점이다. 정점을 지우고자 할 때, re[]를 맨 마지막 정점부터 역추적하기 때문에 처음 데이크스트라를 $E$번 노드부터 진행하면 사전순으로 제일 앞에 오는 최단 경로를 쉽게 구해낼 수 있다. re[]를 추적할 때, 가장 최소 번호만 따라가면 되기 때문이다.

다시 $E$번 노드부터 데이크스트라를 진행한 뒤 결과값을 구한다.