백준 3176번 도로 네트워크

< 백준 3176번 도로 네트워크 - 마포 코딩박 >

사용한 알고리즘: LCA


 N개의 도시들과 각 도시를 연결하는 N-1개의 도로에 대한 정보가 입력됩니다. K개의 입력으로 주어지는 도시쌍 a,b 에 대해 a,b를 연결하는 도로들 중 최대, 최소 값을 구하는 문제였습니다.

문제풀이는 다음과 같습니다.

(1) (코드 13~16)
 LCA 기본 구현에 쓰이는 'parent[i][k] : i의 2^k 번째 조상' 개념에 더불어 'Value[i][k] : i의 2^k 조상으로 갈 때 <최소길이, 최대길이>' 라는 pair 배열을 추가로 설정해줍니다.

(2) (코드 19~33)
 1번 도시를 root라 생각하고 depth[1]=1 라 하고 모든 노드의 depth를 설정해줍니다.
 이때 parent[i][0] 는 자신의 부모가 되고, Value[i][0] = <부모까지거리, 부모까지거리> 가 됩니다.

(3) (코드 47~59)
 기본적인 LCA 의 parent[i][k] 를 계산하는 과정에서 추가로 Value[i][k] 값도 함께 계산해 줍니다.

(4) (코드 60~97)
 K번 입력되는 도시 a,b 의 공통 조상을 찾아가며, 앞서 계산해 둔 Value[i][k] 값을 통해 a,b 사이 도로의 최소, 최대 값을 최신화 해줍니다.