[백준] No.3176 - 도로 네트워크 (C++, 최소 공통 조상)

문제

 

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

3176번: 도로 네트워크

 

풀이

 

solved.ac 난이도: Platium 4

 

 

DP를 이용한 최소 공통 조상 알고리즘을 사용하여 해결하는 문제.

해당 문제는 LCA 2(11438)와 정점들의 거리(1761)에서 사용한 풀이에서 도로의 최소, 최대를 저장하는 계산만 추가하면 해결할 수 있다. 

 

x의 2^k(2의 k승) 번째 조상까지의 최소 도로를 min_road[x][k]라고 하자.

 

min_road[x][k]는 아래와 같은 점화식으로 구할 수 있다.

min_road[x][k] = min(min_road[parent[x][k-1]][k-1], min_road[x][k-1]);

즉, x의 2^(k-1)번째 조상에서 2^(k-1)번째 조상까지의 최소 도로와

x에서 2^(k-1)번째 조상까지의 최소 도로를 비교하여 더 작은 값이 x에서 2^k번째 조상까지의 최소 길이의 도로이다.

 

아래의 트리에서 5번 노드의 4번째 조상까지의 최소 길이의 도로를 구해보자.

 

min_road[5][0] = 40, min_road[4][0] = 30, min_road[3][0] = 20, min_road[2][0] = 10,

각 노드에서 2^0번째 조상은 첫번째 조상, 바로 위의 부모 노드이다.

 

min_raod[5][1] = min( min_road[parent[5][0]][0], min_road[5][0] ) = min( min_road[4][0], min_road[5][0] ) = 30

min_road[3][1] = min( min_road[parent[3][0]][0], min_road[3][0] ) = min( min_road[2][0], min_road[3][0] ) = 10

 

min_road[5][2] = min( min_road[parent[5][1]][1], min_road[5][1] )

=  min( min_road[3][1], min_road[5][1] ) = 10

min_road[5][2]는 min_road[3][1]와 min_road[5][1]로 나뉜다.위의 그림에서는 해당 구간에서 최소 도로 값을 저장하고 있음을 표현했다.

 

최대 길이의 도로도 이와 마찬가지로  x의 2^k(2의 k승)번째 조상까지의 최대 도로를 max_road[x][k]에 저장하자.

 

이제 각 노드에서 LCA까지 이동하면서 각 구간의 최대, 최소의 도로를 구해 비교하면 된다. 

 

LCA에 대한 더 자세한 풀이는 위에서 소개한 두 문제를 참조하자.

LCA 2(11438), 정점들의 거리(1761)

코드