알고리즘 - 최소 공통 조상(LCA, Lowest Common Ancestor)

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

---

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

일반적으로 구하는 방법과 빠르게 구하는 방법이 있다.

 

일반적인 최소 공통 조상 구하기

---

먼저 일반적인 최소 공통 조상 구하기를 사용하려면 트리의 높이가 크지 않은지 판단해야 한다.

최소 공통 조상은 트리의 높이가 시간 복잡도에 많은 영향을 주기 때문에 트리의 높이가 높지 않은 경우에 사용한다.

일반적인 최소 공통 조상 구하기

예시로 4번 노드와 15번 노드의 공통 조상을 찾는다고 해보자

먼저 루트 노드에서 탐색을 시작해 각 노드의 부모 노드와 깊이를 저장해야 한다. 여기서 트리라는 특징을 잘 활용하면 바로 직전 탐색 노드가 부모 노드가 된다는 것을 알 수 있고, 해당 노드의 차수를 구할 수 있다.

탐색은 DFS, BFS를 이용해 수행한다.

깊이 맞추기

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

위의 사진을 보면 더 깊은 노드인 15의 부모를 1개씩 올려 주면서 4번 노드와 깊이는 맞췄지만, 값이 다르기 때문에 공통 조상이라고 할 수 없다.

같은 노드가 될 때까지 반복하기

따라서, 깊이가 같은 상태에서는 동시에 부모 노드로 올라가면서 두 노드가 같은 노드가 될 때까지 반복하고 이 때 처음 만나는 노드가 최소 공통 조상이 된다.

위와 같은 방식을 이용하면 최소 공통 조상을 구할 수 있지만, 트리의 높이가 커질 경우 시간 제약 문제에 직면할 수 있다. 이러한 문제를 해결하기 위해 새롭게 제안된 방법이 빠르게 최소 공통 조상 구하기다.

 

빠르게 최소 공통 조상 구하기

---

핵심은 서로의 깊이를 맞춰 주거나 같아지는 노드를 찾을 때 기존에 한 단계씩 올려 주는 방식에서 2^k 씩 올라가 비교하는 방식이다.

기존에 자신의 부모 노드만 저장해 놓던 방식에서 2^k번째 위치의 부모 노드까지 저장해 둬야 한다.

 

빠르게 최소 공통 조상 핵심

1. 부모 노드 저장 배열 만들기

부모 노드 저장 배열

2^k 씩 올라가기 위해서는 2^k에 어떤 부모가 있는지를 알아야 한다.

따라서, 부모 노드 배열을 정의하고 점화식을 도출해야 한다.

K는 트리의 깊이 > 2^k 을 만족하는 최댓값을 의미한다.

부모 노드 배열의 정의: P[K][N] - N번의 노드의 2^k 번째 부모의 노드 번호

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

위의 예시를 통해서 k = 2, N = 12를 점화식으로 풀어보면

P[2][12] = P[1][P[1][12]]

==> P[1][12] = P[0][P[0][12]] ==> P[1][12] = P[0][6]  ※ P[1][12] = 6

==> P[2][12] = P[1][6]  ※ P[2][12] = 1

 

2. 선택된 두 노드의 깊이 맞추기

어떤 두 개의 노드를 선택하여 깊이를 맞추기 위해서는 2^k의 단위로 점프하면서 맞춘다.

2와 15의 최소 공통 조상을 찾는다고 가정하면 먼저 트리에서 더 깊이 있는 15번 인덱스를 앞선 점화식을 통해 2번 노드와 깊이를 맞춰야한다. 

 

3. 최소 공통 조상 찾기

2^k의 단위로 점프하면서 깊이를 먼저 맞춘 후 k값을 1씩 감소하면서 P 배열을 이용해 최초로 두 노드의 부모가 달라지는 값을 찾는다.

같은 깊이에 위치한 14번 노드와 15번 노드의 최소 공통 조상을 찾는다고 가정하면

k의 값은 2²을 넘어갈 수 없기 때문에 k를 2로 설정하고 점화식을 통해서 구해본다.

P[2][14] 와 P[2][15]의 값이 같기 때문에 k값을 1 감소시켜 다시 비교해본다.

P[1][14]는 10이고 P[1][15]는 11이기 때문에 최초로 두 노드의 부모가 달라지는 것을 알 수 있고 6번 노드가 최소 공통 조상이라는 것을 알 수 있다.

반복이 종료된 후 이동한 2개의 노드가 같은 노드라면 해당 노드가, 다른 노드라면 바로 위의 부모 노드가 최소 공통 조상이 된다.

추가 예시

만약에 위의 예시에서 사진과 같이 16번, 17번 노드가 있다고 가정해보고 16과 17의 최소 공통 조상을 구해보면

P[2][16]과 P[2][17]은 똑같이 6번 노드를 가리키게 된다. 값이 같기 때문에 k를 1씩 낮추는 것을 반복하면

P[1][16]과 P[1][17]을 비교하면 12와 13이 나오게 되고 값이 다르기 때문에 해당 노드로 이동하게 된다.

마지막으로 이동한 위치에서 k 값을 1 낮춰 P[0][12] 와 P[0][13]을 비교하면 10과 11로 값이 같지 않게 되고 해당 노드로 이동하고 반복이 종료되지만 해당 노드의 바로 위 부모가 최소 공통 조상이 된다.