[BOJ] 3176번: 도로 네트워크 (C++) [Platinum Ⅳ]

[BOJ] 3176번: 도로 네트워크 (C++) [Platinum Ⅳ]

첫째 줄에 N이 주어진다. (2 ≤ N ≤ 100,000) 다음 N-1개 줄에는 도로를 나타내는 세 정수 A, B, C가 주어진다. A와 B사이에 길이가 C인 도로가 있다는 뜻이다. 도로의 길이는 1,000,000보다 작거나 같은 양

부끄럽지만 문제를 이해하는데 시간이 조금 걸렸다. 필자처럼 문제를 이해하는데 헤매는 사람이 있을 수도 있으니 문제에 대해 정리해보겠다.

예제 입력 1을 시각화하면 다음과 같다. 이때 도시 1과 도시 2를 연결하는 경로는 2-3-1로 길이가 100인 도로와 길이가 50인 도로로 이루어져 있다. 따라서 도시 1과 도시 2를 연결하는 경로에서 가장 짧은 도로의 길이는 50, 가장 긴 도로의 길이는 100이다.

N개의 노드와 N-1개의 간선으로 이루어져 있으므로 트리 구조다.

트리 구조에서 노드 A와 노드 B사이의 경로를 파악하는 문제는 LCA(Least Common Ancestor) 알고리즘을 통해 각 쿼리당 O(logN) 안에 해결할 수 있다.

기존의 LCA 알고리즘은 length 배열에 2i번째 부모까지의 길이를 저장한다.

이를 변형하여 minLength 배열에는 2i번째 부모까지의 경로 중 가장 짧은 도로의 길이 를 저장하고 maxLength 배열에는 2i번째 부모까지의 경로 중 가장 긴 도로의 길이 를 저장하여 문제를 해결할 수 있다.

from http://gibro.tistory.com/6 by ccl(A) rewrite - 2021-12-18 17:26:53