[D-7] 최소 공통 조상

📍 최소 공통 조상

✅ 정의

트리 그래프에서 처음 공통으로 만나게 되는 부모 노드를 뜻한다.
임의의 두 노들르 선택했을 때 두 노드가 각각 자신을 포함해 거슬러 올라가면서 부모노드를 탐색할 때 부르는 뜻이다.

 

✅ 핵심 이론

일반적인 최소 공통 조상 구하기
- 주로 트리의 높이가 크지 않을 때 구하는 방법이다.
- 트리의 높이가 커질 경우, 시간 제약 문제에 직면할 수 있다. 이 경우 아래의 '최소 공통 조상 빠르게 구하기' 방법을 이용한다.

✔️ 선택된 두 노드의 깊이가 다른 경우,
    더 깊은 노드의 노드를 부모 노드로 1개씩 올려주면서 같은 깊이로 맞춘다.
    이 때 두 노드가 같으면 해당 노드가 최소 공통 조상이므로 탐색을 종료한다.

---

 

✔️ 선택된 두 노드의 깊이가 같은 경우,
     동시에 부모 노드로 올라가면서 두 노드가 같은 노드가 될 때까지 반복한다.
     이 때 처음 만나는 노드가 최소 공통 조상이 된다.

---

최소 공통 조상 빠르게 구하기
- 서로의 깊이를 맞춰 주거나 같아지는 노드를 찾을 때 기존 한 단계씩 올려 주는 방식에서 2^k씩 올라가 비교하는 방식이다.
- 기존에 자신의 부모 노드만 저장해 놓던 방식에서 2^k번째 위치의 부모 노드까지 저장해둬야 한다.

1. 부모 노드 저장 배열 만들기
- 점화식에서 N의 2^K번째 부모 노드는 N의 2^K-1번째 부모 노드의 2^K-1번째 부모 노드라는 의미이다.
- K = 4일 경우 N의 16번째 부모 노드는 N의 여덟 번째 부모 노드의 여덟 번째 부모 노드라는 의미이다.

// 부모 노드 배열의 정의
P[K][N] = N번 노드의 2^k번째 부모의 노드 번호​

// 부모 노드 배열의 점화식
P[K][N] = P[K-1][P[K-1][N]]​

 

2. 선택된 두 노드의 깊이 맞추기
- P배열을 이용해 기존에 한 단계씩 맞췄던 깊이를 2^K단위로 넘어가면서 맞춘다.

3. 최소 공통 조상 찾기
- 공통 조상을 찾는 작업 역시 한 단계씩이 아닌 2^k 단위로 점프하면서 맞춘다.
- k값을 1씩 감소하면서 p배열을 이용해 최초로 두 노드의 부모가 달라지는 값을 찾는다.
- 최초로 달라지는 k에 대한 두 노드의 부모 노드를 찾아 이동한다.
- 반복문이 종료된 후 이동한 2개의 노드가
   같은 노드라면 해당 노드가,
   다른 노드라면 바로 위의 부모 노드가 최소 공통 조상이 된다.