트리 그래프에서 임의의 두 노드를 선택했을 때 두 노드가 각각 자신을 포함해 거슬러 올라가면서 부모 노드를 탐색할 때 처음 공통으로 만나게 되는 부모 노드를 '최소 공통 조상(LCA : lowest common ancestor)'이라고 한다.
일반적인 최소 공통 조상 구하기
트리의 높이가 크지 않을 때 최소 공통 조상을 구하는 방법이다.
다음과 같은 트리에서 4번 15번 노드의 최소 공통 조상을 구해 보겠다.
먼저 루트 노드에서 탐색을 시작해 각 노드의 부모 노드와 깊이를 저장한다. 이때 탐색은
DFS 혹은 BFS을 이용해 수행한다.
선택된 두 노드의 깊이가 다른 경우, 더 깊은 노드의 노드를 부모 노드로 1개씩 올려 주면서 같은 깊이로 맞춘다. 이때 두 노드가 같으면 해당 노드가 최소 공통 조상이므로 탐색을 종료한다.
깊이가 같은 상태에서는 동시에 부모 노드로 올라가면서 두 노드가 같은 노드가 될 때까지 반복한다. 이때 처음 만나는 노드가 최소 공통 조상이 된다.
위와 같은 방식을 이용하면 최소 공통 조상을 구할 수 있지만, 트리의 높이가 커질 경우, 시간 제약 문제에 직면할 수 있다.
최소 공통 조상 빠르게 구하기
'최소 공통 조상 빠르게 구하기'의 핵심은 서로의 깊이를 맞춰 주거나 같아지는 노드를 찾을 때 기존에 한 단계씩 올려 주는 방식에서 씩 올라가 비교하는 방식이다. 따라서 기존에 자신의 부모 노드만 저장해 놓던 방식에서 번째 위치의 부모 노드까지 저장해 둬야 한다.
1. 부모 저장 배열 만들기
부모 노드 배열을 만들기 위해서는 부모 노드 배열의 정의와 점화식을 알아야 한다.
부모 노드 배열의 정의
- P[N][K] = N번 노드의 번째 부모의 노드 번호
부모 노드 배열의 점화식
- P[N][K] = P[N - 1][P[K - 1][N]]
점화식에서 N의 번째 부모 노드는 N의 번째 부모 노드의 번째 부모 노드라는 의미다. 즉 K = 4 라고 가정하면 N의 16번째 부모 노드는 N의 8번째 부모 노드의 8번째 부모 노드라는 의미다.
배열에서 K는 '트리의 깊이 > ' 를 만족하는 최댓값이다.
다음과 같은 트리에서 최대 깊이는 5이기 때문에 K = 2가 된다. 즉 이 트리의 모든 노드는 번째 부모 노드를 지니고 있는 경우가 없다.
부모 노드 배열의 점화식을 이용해 배열의 값을 채워보았다.
초기화된 K=0 배열을 바탕으로 K를 1씩 증가시키며 나머지 배열을 채운다.
예시를 위한 P[2][14]를 구하는 과정이다.
2. 선택된 두 노드의 깊이 맞추기
P배열을 이용해 기존에 한 단계씩 맞췄던 깊이를 단위로 넘어가면서 맞춘다.
예를 들어 노드 2와 노드 15의 깊이를 맞춰 보겠다.
노드 2의 깊이는 2, 노드 15의 깊이는 6으로 두 노드의 깊이 차는 4이다. 깊이를 맞추기 위해 더 깊게 있는 노드 15의 4번째 부모 노드를 P배열을 이용해 찾는다. 4 = 이므로 K = 2 이고 P[2][15] = 3이므로 노드 3으로 이동하면 노드 2와 높이를 맞추게 된다.
만약 높이 차이가 20이라고 가정하면 ≤ 20을 만족하면서 K가 최대가 되는 만큼 이동하면서 높이 차가 0이 될 때까지 반복한다. 즉, (20) -> (4)와 같이 두 번 이동한다.
3. 최소 공통 조상 찾기
공통 조상을 찾는 작업 또한 한 단계씩이 아니라 단위로 점프하면서 맞춘다. K 값을 1씩 감소하면서 P배열을 이용해 최초로 두 노드의 부모가 달라지는 값을 찾는다.
최초로 달라지는 K에 대한 두 노드의 부모 노드를 찾아 이동한다. 즉, 노드 10, 노드 11로 이동한다. 이를 K가 0이 될 때가지 반복한다.
반복문이 종료된 후 이동한 2개의 노드가 같은 노드라면 해당 노드가, 다른 노드라면 바로 위의 부모 노드가 최소 공통 조상이 된다
여기서는 노드 10, 11이 다른 노드이기 때문에 바로 위 노드를 뜻하는 P[0][10] 또는 P[0][11], 즉 노드 6이 최소 공통 조상이 된다.
- Do it! 알고리즘 코딩테스트 자바 편
