트리, 최소공통조상(LCA, Lowest Common Ancestor)

최소 공통 조상

# 정의 : 트리 구조에서 임의의 두 정점이 갖는 가장 가까운 조상 정점을 의미한다.

 

이 알고리즘을 만드는 방법은 2가지가 있다.

1. LCA를 선형 탐색으로 구하기 -> O(Depth)

2. LCA를 이분 탐색으로 구하기 -> O(log(Depth))

 

# LCA를 선형 탐색으로 구하기

공통 조상을 찾기위한 가장 단순한 방법으로는, 두 정점에 포인터를 두고 가리키는 정점이

같아질때까지 부모 노드로 거슬러 올라가면 된다.

parent[x]를 정점 x의 부모 노드라 할 때, x = parent[x] 연산을 반복하다보면 두 개의 포인터가

같은 정점을 가리키게 됐을 때 공통 조상을 찾은 것이다.

주의할 점은 두 정점의 LEVEL이 다르다면 문제가 발생한다.

하나는 LEVEL이 3인데 다른 것은 LEVEL이 5라면 같이 올라갈 때 LEVEL 3이 먼저 발견하지만

같은 정점을 가리키지 않게 돼 올바른 조상을 지나쳐가게 된다.

그래서 두 정점의 깊이를 동일하게 맞춰줘야 한다.

LEVEL이 5라면 LEVEL이 3이 되도록 2번 부모 노드를 찾아 같은 LEVEL 3가 되도록 하는 것이다.

LEVEL이 같아졌으니 부모 노드로 거슬러 올라가면 공통 조상을 찾게 된다.

 

# LCA를 이분 탐색으로 구하기

이 방법은 이분탐색이라 O(log(Depth))로 빠르게 해결할 수 있다.

Parent 배열을 2차원으로 두어, parent[x][k] 를 x번 정점의 2^k번째 조상 노드의 번호로 생각하자

나중에 알게됐는데 이 방법을 희소 배열이라고 한다. 그래서 관련한 글을 추가로 작성해야겠다.

그리고 트리를 구성하게 되면 낮은 깊이의 노드부터 탐색하므로

parent[x][k] = parent[parent[x][k-1]][k-1] 이 성립하게 된다.

 

부모 노드로 거슬러가는 과정을 2의 제곱수만큼 한 번에 건너뛸 수 있다.

두 정점을 같은 깊이로 맞추기 위해 2^k만큼 건너뛰고 같은 깊이로 맞춰주면 된다.