1595. 북쪽나라의 도로#
관찰#
문제에서는,
임의의 두 도시 사이를 이동하는 경로가 항상 유일하도록 도로가 설계되어 있다.
이는 곧 전체 도로망이 트리임을 의미한다.
또 문제의 요구사항은 가장 멀리 떨어진 두 도시 사이의 거리를 구하는 것인데,
이는 전형적인 트리의 지름 문제로 환원된다.
트리의 지름은,
- 임의의 정점에서 DFS를 수행해 가장 먼 정점 A를 찾는다.
- 정점 A에서 다시 DFS를 수행하여 가장 먼 정점까지의 거리를 구한다.
- 2에서 구한 거리가 트리의 지름이다.
일반적인 트리의 지름 문제는
지나가는 정점의 개수나, 정점에서의 가중치 합을 설명하는 경우가 많은데,
여기서는 각 도로에 가중치가 부여되어 있으므로,
DFS 과정에서 누적 거리 합을 기준으로 가장 먼 정점을 판단해야 했다.
따라서 인접 리스트를 구성할 때, (다음 정점, 가중치) 형태로 저장했다.
시간 복잡도#
해당 문제의 조건은
\( V \le 10{,}000 \) 이고,
트리에서의 간선의 개수는 \( E = V-1 \) 이다.
DFS 의 시간 복잡도는 \( O (V+E) \) 이므로,
2번의 DFS를 충분히 여유롭게 수행할 수 있다.