[BOJ] 3584 가장 가까운 공통 조상

3584번: 가장 가까운 공통 조상

문제

루트가 있는 트리(rooted tree)가 주어지고, 그 트리 상의 두 정점이 주어질 때 그들의 가장 가까운 공통 조상(Nearest Common Anscestor)은 다음과 같이 정의됩니다.

• 두 노드의 가장 가까운 공통 조상은, 두 노드를 모두 자손으로 가지면서 깊이가 가장 깊은(즉 두 노드에 가장 가까운) 노드를 말합니다.

예를 들어  15와 11를 모두 자손으로 갖는 노드는 4와 8이 있지만, 그 중 깊이가 가장 깊은(15와 11에 가장 가까운) 노드는 4 이므로 가장 가까운 공통 조상은 4가 됩니다.

루트가 있는 트리가 주어지고, 두 노드가 주어질 때 그 두 노드의 가장 가까운 공통 조상을 찾는 프로그램을 작성하세요

입력

첫 줄에 테스트 케이스의 개수 T가 주어집니다.

각 테스트 케이스마다, 첫째 줄에 트리를 구성하는 노드의 수 N이 주어집니다. (2 ≤ N ≤ 10,000)

그리고 그 다음 N-1개의 줄에 트리를 구성하는 간선 정보가 주어집니다. 한 간선 당 한 줄에 두 개의 숫자 A B 가 순서대로 주어지는데, 이는 A가 B의 부모라는 뜻입니다. (당연히 정점이 N개인 트리는 항상 N-1개의 간선으로 이루어집니다!) A와 B는 1 이상 N 이하의 정수로 이름 붙여집니다.

테스트 케이스의 마지막 줄에 가장 가까운 공통 조상을 구할 두 노드가 주어집니다.

출력

각 테스트 케이스 별로, 첫 줄에 입력에서 주어진 두 노드의 가장 가까운 공통 조상을 출력합니다.

---

얼마 전에 익혔던 LCA 알고리즘 문제를 다시 풀어봤다. 공부한지 별로 안 지난 것 같은데 가물가물했다. 이렇게 복습하고 지나가지 않으면 매번 그냥 까먹게 되는 것 같다. 

 

LCA 알고리즘을 요약하면 각 트리 노드들의 깊이를 미리 구해두고 LCA을 구하기 위해 같은 깊이로 맞춰준 다음, LCA를 찾을 때까지 올라간다. 이때 2, 4, 8처럼 2^n번째 부모를 미리 구해두면 더 빠르게 LCA를 구할 수 있다. 어느 정도 수준까지 미리 구해놓느냐는 트리의 최대 크기에 달렸다. ceil(log2n(트리 최대 크기)) 이걸 사용해서 구하면 된다.

 

 

후기)

확실히 백준 문제가 요새 풀고 있는 삼성 역량 테스트 문제에 비해 훨씬 가볍다. 최적화가 거의 필요없기도 하지만 애초에 요구사항이 훨씬 적다. 삼성 문제만 풀다가 백준 문제 푸니까 살 것 같다.