[BOJ 23807] 백준 23807번 - 두 단계 최단 경로 3

1. 문제

$23807$. 두 단계 최단 경로 3

백준 23807번 - 두 단계 최단 경로 3 (https://www.acmicpc.net/problem/23807)

2. 풀이

어느 한 점에서 다른 한 점으로 가는 최단거리를 구하는 문제이므로, Dijkstra 다익스트라 알고리즘을 사용한다.

두 단계 최단 경로 1, 2와 비슷한 문제지만, 어떤 그리디한 방법이 있는 것은 아니다. 물론 처음에는 그리디한 방법을 찾고자 했다. 그러나 시간 제한(6초)과 메모리 제한(1024MB)을 보고 브루트포스 알고리즘인 것 같아 그리디한 방법을 찾는 것을 빠르게 포기했다.

세 개의 정점을 반드시 거치는 것이면, 그 임의의 정점을 $A, B, C$라고 가정했을 때 $X \rightarrow A + A \rightarrow B $ $+\; B \rightarrow C + C \rightarrow Z$ 거리 합의 최솟값을 모든 $A, B, C$ 정점에 대해서 구하면 된다. 이는 $X, A, B, C$ 각각에 대해서 다익스트라를 돌린 Dist 값들이 필요하다는 의미이다. 따라서 $X$와 $P$개의 $Y$(총 $P+1$번)에 대해서 다익스트라를 돌려야 한다.

$3\leq P\leq min(100, N-3)$ 이므로 $P$의 최댓값은 $100$이다. 따라서 다익스트라를 최대 $101$번($X$ 포함) 돌리게 된다. 시간복잡도는 $O(ElogV)$ $ \times 101(최대노드수) $ $= 300,000$ $\times log(100,000) \times 101 $ $= 500,000,000$ 대략 5억이 나온다. 1초당 1억번의 연산을 한다고 가정하면 5초의 시간이 소요되므로 시간 제한인 6초에 부합한다.

메모리는 각각의 정점에 대한 Dist vector가 101개 존재해야 하므로 $8byte(long \; long \; int)$ $ \times 100,000(N)$ $ \times 101(최대노드수) $ $= 80,000,000byte $ $= 80MB$ 대략 $80MB$여서 메모리 조건인 $1024MB$에도 부합한다.

$P$개중 세 개의 노드를 선택하는 것은 간단하게 삼중반복문을 사용하였다.

3. 채점 결과

4. 회고

.

5. 코드