최소공통조상

트리 그래프에서 임의의 두 노드를 선택했을 때, 두 노드가 각각 자신을 포함해 거슬러 올라가면서 부모 노드를 탐색할 때, 처음 공통으로 만나게 되는 부모 노드를 최소 공통 조상(LCA : Lowest Common Ancestor)이라고 한다. 

핵심 이론 - 배열 형성 > 높이 맞추기 > 찾기

1. 일반적인 최소 공통 조상 구하기 
먼저 트리의 높이가 크지 않을 때 LCA를 구하는 방법을 예시와 함께 알아보자. 특정 트리에서 두 개의 노드를 임의로 정한 다음 각 노드의 깊이와 부모 노드를 찾아보자. 이때는 DFS or BFS를 이용해 탐색을 수행한다. 

선택된 두 노드의 깊이가 다른 경우, 더 깊은 깊이의 노드를 해당 노드의 부모 노드로 1개씩 올려주면서 같은 깊이로 맞춰준다. 이때 만일 두 노드가 같아지면 해당 노드가 LCA이므로 탐색을 종료한다.

깊이를 맞춰준 경우 두 노드를 동시에 부모 노드로 올라가면서 두 노드가 같은 노드가 될 때까지 반복한다. 이때 처음으로 만나는 노드가 LCA가 된다. 

 

위와 같은 방법으로 해결할 수 있겠지만, 가장 첫줄에 필자가 적어둔 전제하에서만 사용할 것이다. 트리의 높이가 커질 경우, 시간적인 제약으로 인해 효율성이 떨어지기 때문이다.(양끝 리프 노드를 잡았다고 치면 어느 세월에 다 올라가...?ㅋ)

 

2. 빠르게 최소 공통 조상 구하기
이번 방법의 핵심은 1번과 비슷하지만 약간 변형한 방식으로 깊이를 1씩 증가시키는 것이 아니라, 2^k씩 올라가면서 비교하는 방식이다.  따라서 1번과 달리 특정 노드의 깊이와 부모노드를 저장하는 것이 아니라, 깊이와 2^k번째 위치의 부모노드까지 저장해 둬야 한다.

 

(1) 부모 노드를 저장할 배열 만들기 (점화식을 이해하자)
P [K][N] = N번 노드의 2^k번째 부모의 노드 번호

부모 노드 배열의 점화식
P [K][N] = P [K - 1][P [K-1][N]]
-> N번 노드의 2^k번째 부모의 노드 번호는 N의 k-1번째 부모 노드의 2^(k-1) 번째 부모 노드라는 뜻이다.

예를 들어 k=4라고 한다면, N의 16번째 부모 노드의 번호는 N의 여덟 번째 부모 노드의 여덟째 부모 노드라는 뜻이다.
이때, k는 '트리의 깊이 > 2^k'을 만족시키는 최댓값이어야 한다. 깊이는 루트를 0으로 해서 리프 노드까지 카운트한다.

 

위와 같은 트리가 있다고 할 때, 트리의 깊이는 5이기 때문에, K = 2가 된다. 즉, 이 트리의 모든 노드는 2^3 번째 부모 노드를 지니고 있는 경우가 없다.

위의 점화식을 참고해서 배열을 완성해보자.

1	2	3	4	5	6	7	8	9	10	11	12	13	14	15	노드
	1	1	2	2	3	3	4	4	6	6	11	11	13	13	0
			1	1	1	1	2	2	3	3	6	6	11	11	1
											1	1	3	3	2

하나의 예로 점화식에 의거해 14번 노드의 4번째 부모 노드를 구해보자. P [2][14]가 될 것이다. 
P[2][14] = P [1][P [1][14]]
P [1][14] = P[0][P [0][14]] => P[0][14] 은 13이므로 P [0][13] = 11
따라서 P [2][14] = P [1][11]

P [1][11] = P [0][P [0][11]] = P [0][6] = 3

 

(2) 선택된 두 노드의 깊이 맞추기
위의 P배열을 이용해 기존에 한 단계씩 맞추었던 깊이를 2K 단위로 넘어가면서 맞춘다. 예를 들어 2번 노드와, 15번 노드의 공통 조상을 찾기 위해 깊이를 맞춰보자.

노드 2의 깊이는 1, 노드 15의 깊이는 5로 깊이 차이는 4(네 번째 부모 노드를 찾아야 한다.)이다.
더 깊이 있는 15번 노드의 4번째 부모 노드를 깊이를 맞추기 위해 P배열을 이용해 찾아보자. 
P [2][15]가 될 것이다. 결과는 3이 된다. 즉, 노드 3으로 이동하면 2번 노드와 높이를 맞출 수 있다.

예시와 같이 높이 차이가 2의 거듭제곱으로 떨어진다면, 계산이 편리해서 좋겠지만, 그렇지 않은 경우는 아래와 같이 하면 된다. 
만일 높이 차이가 20이라고 가정하면 2^k <= 20을 만족하면서 K가 최대가 되는 만큼 이동하면서 높이 차이가 0이 될 때까지 반복한다.  2^4(20) -> 2^2(4)와 같이 2번 이동하면 높이를 맞출 수 있다.

(3) LCA 찾기 
공통 조상을 찾는 작업 역시 2K 단위로 점프하면서 맞춘다. 먼저 P배열을 이용해서 두 노드의 2^k번째 부모 노드가 최초로 같아지는 값을 찾는다. 

위 결과의 의미는 LCA(14, 15)가 2^1 ~ 2^2 사이에 존재한다는 뜻이다. 따라서 최초로 같아지는 K값보다 1개 작은 곳(K=1)으로 이동한다.  

위를 반복(예시와는 다르게 트리의 높이가 크다면 2^n ~ 2^(n+1) 사이의 노드는 몇 개일지 장담할 수 없기 때문에 반복을 통해서 그 범위를 줄여나가야 한다. 이로써 1단계씩 거슬러 오르며 찾는 것보다 훨씬 빠르게 찾을 수 있다.)하면서 K=0 또는 K=1일 때 같은 값이 나오면 해당 값이 LCA가 되고 알고리즘이  종료된다. 

 

문제 풀이는 다음 시간에....