[BOJ] 11437 LCA

11437번: LCA

문제

N(2 ≤ N ≤ 50,000)개의 정점으로 이루어진 트리가 주어진다. 트리의 각 정점은 1번부터 N번까지 번호가 매겨져 있으며, 루트는 1번이다.

두 노드의 쌍 M(1 ≤ M ≤ 10,000)개가 주어졌을 때, 두 노드의 가장 가까운 공통 조상이 몇 번인지 출력한다.

입력

첫째 줄에 노드의 개수 N이 주어지고, 다음 N-1개 줄에는 트리 상에서 연결된 두 정점이 주어진다. 그 다음 줄에는 가장 가까운 공통 조상을 알고싶은 쌍의 개수 M이 주어지고, 다음 M개 줄에는 정점 쌍이 주어진다.

15
1 2
1 3
2 4
3 7
6 2
3 8
4 9
2 5
5 11
7 13
10 4
11 15
12 5
14 7
6
6 11
10 9
2 6
7 6
8 13
8 15

출력

M개의 줄에 차례대로 입력받은 두 정점의 가장 가까운 공통 조상을 출력한다.

2
4
2
1
3
1

 

---

SWEA에서 올려준 문제를 푸느라 공부한 LCA 알고리즘을 백준에서 한번 더 풀어봤다. 트리를 거꾸로 올라가기 위해서 부모를 저장하는건 그렇다고 치지만 2^k 위의 부모까지 저장해놓는 아이디어가 진짜 대단한 것 같다. 그리고 깊이 값을 잘 사용하면 두 노드 사이의 거리를 구하는 것도 상당히 쉬워진다. 

 

LCA를 구하기 위해 작성한 함수는 두 노드의 값을 입력 받으면 우선 두 노드의 깊이 값을 확인해서 깊이가 더 깊은 노드를 깊이가 낮은 노드 수준까지 올려준다. 이 파트도 비트 연산을 활용해서 처리하는게 인상적이었다. 이후 두 노드의 부모 값을 비교해가면서 LCA 바로 밑 노드에서 멈추고 그 노드의 하나 위 부모를 리턴해준다.

 

 

후기)

최소 공통 조상이라는 말로 들으면 별거 없어보이지만 진짜 깊은 맛이 있는 알고리즘이었다.