트리 그래프에서 임의의 두 노드를 선택했을 때 두 노드가 각각 자신을 포함해 거슬로 올라가면서 부모 노드를 탐색할 때 처음 공통으로 만나게 되는 부모 노드를 ‘최소 공통 조상(LCA: Lowest Common Ancestor)’라고 한다.
먼저 트리의 높이가 크지 않을 때 최소 공통 조상을 구하는 방법. 다음 예시에서는 4번, 15번 노드의 최소 공통 조상을 구한다.
먼저 루트 노드에서 탐색을 시작해 각 노드의 부모 노드와 깊이를 저장한다.
선택된 두 노드의 깊이가 다른 경우, 더 깊은 노드의 노드를 부모 노드로 1개씩 올려 주면서 같은 깊이로 맞춘다. 이때 두 노드가 같으면 해당 노드가 최소 공통 조상이므로 탐색을 종료한다.
깊이가 같은 상태에서는 동시에 부모 노드로 올라가면서 두 노드가 같은 노드가 될 때까지 반복한다. 이때 처음 만나는 노드가 최소 공통 조상이 된다.
이런 원리로 다음 트리에서 4번, 15번 노드의 최소 공통 부모는 1이 된다.
위와 같은 방식을 이용하면 최소 공통 조상을 구할 수 있지만, 트리의 높이가 커질 경우, 시간 제약 문제에 직면할 수 있다. 이런 문제를 해결하기 위해 새롭게 제안된 방식이 최소 공통 조상 빠르게 구하기다. 일반적인 최소 공통 조상 구하기 알고리즘을 약간 변형한 형태이므로 최소 공통 조상 구하는 원리를 정확하게 학습하고 넘어가야 한다.
‘최소 공통 조상 빠르게 구하기’의 핵심은 서로의 깊이를 맞춰 주거나 같아지는 노드를 찾을 때 기존에 한 단계씩 올려 주는 방식에서 $2^k$씩 올라가 비교하는 방식이다. 따라서 기존에 자신의 부모 노드만 저장해 놓던 방식에서 **$2^k$**번째 위치의 부모 노드까지 저장해 둬야 한다.
부모 노드 저장 배열 만들기
부모 노드 배열을 만들기 위해선 이 배열의 정의와 점화식을 알아야 한다.
<aside> 💡 부모 노드 배열의 정의
P[K][N] = N번 노드의 $2^k$번째 부모의 노드 번호
</aside>
<aside> 💡 부모 노드 배열의 점화식
P[K][N] = P[K - 1][P[K - 1][N]]
</aside>
점화식에서 N의 $2^k$번째 부모 노드는 N의 $2^{k-1}$번째 부모 노드의 $2^{k-1}$번째 부모 노드라는 의미다. 즉, K = 4라고 가정하면 N의 16번째 부모 노드는 N의 여덟 번째 부모 노드의 여덟 번째 부모 노드라는 의미다.
배열에서 K는 ‘트리의 깊이 > $2^k$’를 만족하는 최댓값이다. 다음 트리에서 최대 깊이는 5이기 때문에 K = 2가 된다. 즉, 이 트리의 모든 노드는 $2^3$번째 부모 노드를 지니고 있는 경우가 없다.
부모 노드 배열의 점화식을 이용해 배열의 값을 채운다.
초기화된 배열을 바탕으로 K를 1개씩 증가시키면서 나머지 배열을 채운다. 여기선 이해를 위해 14의 $2^2$번째, 즉 4번째 부모 노드(P[2][14])를 예시로 들음.
P[2][14] = P[1][P[1][14]] ⇒ P[1][14] = P[0][P[0][14]] = P[0][13] = 11 ⇒ P[2][14] = P[1][11] ⇒ P[1][11] = P[0][P[0][11]] = P[0][6] = 3 ∴ P[2][14] = 3
선택된 두 노드의 깊이 맞추기
P 배열을 이용해 기존에 한 단게씩 맞췃던 깊이를 $2^k$ 단위로 넘어가면서 맞춘다.
예를 들어 노드 2와 노드 15의 깊이를 맞춰보자면, 노드 2의 깊이는 2, 노드 15의 깊이는 6으로 두 노드의 깊이 차이는 4다. 깊이를 맞추기 위해 더 깊이 있는 노드 15의 4번째 부모 노드를 P 배열을 이용해 찾는다. 4 = 2²이므로 K=2이고, P[2][15] = 3이므로 노드 3으로 이동하면 노드 2와 높이를 맞추게 된다.
만약 높이 차이가 20이라고 가정하면 $2^K$ ≤ 20을 만족하면서 K가 최대가 되는 만큼 이동하면서 높이 차이가 0이 될 때 까지 반복한다. 즉, 높이 차이가 20일 경우 2⁴(20) → 2²(4)와 같이 두 번 이동하면 된다.
공통 조상을 찾는 작업 역시 한 단계씩이 아닌 $2^K$ 단위로 점프하면서 맞춘다. K값을 1씩 감소하면서 P 배열을 이용해 최초로 두 노드의 부모가 달라지는 값을 찾는다.
P[2][14] = 3 == P[2][15] = 3 P[1][14] = 10 != P[1][15] = 11
최초로 달라지는 K에 대한 두 노드의 부모 노드를 찾아 이동한다. 즉, 노드 10, 노드 11로 이동한다. 이를 K가 0이 될 때까지 반복한다. 반복문이 종료된 후 이동한 2개의 노드가 같은 노드라면 해당 노드가, 다른 노드라면 바로 위의 부모 노드가 최소 공통 조상이 된다.
P[0][0] = 6 == P[0][11] = 6 ∴ LCA(14, 15) = 6