[BOJ 23793] 백준 23793번 - 두 단계 최단 경로 1
1. 문제
$23793$. 두 단계 최단 경로 1
백준 23793번 - 두 단계 최단 경로 1 (https://www.acmicpc.net/problem/23793)
2. 풀이
어느 한 점에서 다른 한 점으로 가는 최단거리를 구하는 문제이므로, Dijkstra(다익스트라 알고리즘)을 사용한다.
$1.$ $Y$를 거쳐가는 경우
$Y$를 거쳐간다는 것은 ‘$X\rightarrow Y\rightarrow Z$ 최단거리’를 구하는 것이므로, 이는 $(X\rightarrow Y 최단거리)+(Y\rightarrow Z 최단거리)$로 나눌 수 있다.
따라서 $X$를 start 지점으로 Dijkstra를 돌려서 최종적으로 나오는 Dist[Y]값, $Y$를 start 지점으로 Dijkstra를 돌려서 최종적으로 나오는 Dist[Z]값을 더하면, $X$에서 출발하여 $Y$를 거쳐서 $Z$에 도달하는 최단거리를 구할 수 있다.
$2.$ $Y$를 거치지 않는 경우
$Y$를 거치지 않는 경우는 Dijkstra를 돌리면서 next(가고자 하는 다음 노드)가 $Y$인 경우 해당 간선 추가 작업을 수행하지 않고 넘어가면 된다.
함수의 재사용성을 극대화하기 위해 함수 하나가 모든 케이스를 다룰 수 있게 만들고자 했다. 따라서 $Y$를 거쳐갈 때는 존재하지 않는 노드인 $0$을 만나면 지나치고, $Y$를 거치지 않는 경우는 $Y$노드를 만나면 지나친다는 식으로 통일하여 코딩했다. (코드 33줄)
3. 채점 결과
4. 회고
처음 제출 때, 코드의 29줄을 작성하지 않아서 TLE(시간초과)를 받았다. 29번 줄의 역할은 pq에서 pop한 노드에 연결된 모든 간선을 탐색하기 전에(코드 30~38줄), dist가 Dist[node] 값을 넘어가지 않는지 검사하는 것이다. 갱신된 작은 값(Dist[node])이 존재하는데 더 큰 값(dist)에서 노드를 추가해 나갈 필요가 없기 때문이다. 따라서 많은 과정을 스킵하여 시간을 줄일 수 있다.
댓글남기기