LCA 알고리즘은 Lowest Common Ancestor의 약자로 트리에서 두 정점에서 가장 가까운 공통 조상을 찾는 알고리즘입니다. 그래프 탐색을 이용한 방법과Dynamic Programming을 이용한 방법 2가지를 정리해보겠습니다.
먼저, 가장 가까운 공통 조상이 무엇인지부터 정의해보겠습니다.
- 조상 : 자기 자신을 포함해 모든 부모 노드를 의미
- 공통 조상 : 어떤 노드 x와 어떤 노드 y의 모든 조상 노드 중 공통된 노드
- 가장 가까운 공통 조상 : 어떤 노드 x와 어떤 노드 y의 공통 조상 노드 중 가장 가까운 노드
정의만 보면 우리가 알고있는 조상의 의미와 똑같아서 어려운게 없습니다. 다만, 자기 자신을 포함한다는 것만 주의하시면 됩니다.
그림과 같은 트리가 있다고 해보겠습니다.
Q . 노드 3번과 노드 10번의 공통 조상은 누구일까요??
노드 3번의 조상은 1, 3, 5번 노드가 입니다.
노드 10번의 조상은 1,5,3,8, 10번 노드입니다.
따라서, 공통 조상은 1, 3, 5번 노드가 되고 가장 가까운 공통 조상은 3번 노드가 됩니다.
공통 조상은 1, 5번 노드가 되고, 가장 가까운 공통 조상은 5번 노드가 됩니다.
트리도 그래프의 일종이므로 그래프 탐색을 이용해서 가장 가까운 공통 조상을 찾을 수 있습니다.
2번 노드와 9번 노드의 가장 가까운 공통 조상을 그래프 탐색을 이용해서 찾아보겠습니다.
1) 2번 노드와 9번 노드 비교
9번 노드가 깊이가 더 깊으므로 부모 노드를 찾아서 탐색을 진행한다.
10번 노드가 깊이가 더 깊으므로 부모 노드를 찾아서 탐색을 진행한다.
3) 2번 노드와 8번 노드 비교
8번 노드가 깊이가 더 깊으므로 부모 노드를 찾아서 탐색을 진행
4) 2번 노드와 3번 노드 비교
깊이가 같으므로 2번 노드가 부모 노드를 찾아서 탐색 진행
5) 5번 노드와 3번 노드 비교
3번 노드가 깊이가 더 깊으므로 부모 노드를 찾아서 탐색을 진행
두 노드가 같아졌으므로 최소 공통 조상은 5번 노드이고, 5번 노드부터 부모 노드를 쭉 탐색해나간다면 조상 노드를 모두 찾을 수 있습니다.
이처럼 우리는 노드의 깊이와 부모 정보만 있다면 그래프 탐색을 이용해서 공통 조상을 찾을 때까지 탐색을 진행할 수 있습니다.
[ 코드 C++ ]
// x와 y 노드의 공통 조상 찾기
while (x != y) {
if (depth[x] > depth[y])
x = parent[x];
else
y = parent[y];
}코드로 표현하면 되게 간단합니다. 두 노드가 같아질 때까지 깊이를 비교해 더 깊은 노드를 계속 부모 노드로 올려주며 탐색을 진행하면 됩니다.
그러면 이 알고리즘의 복잡도는 어떻게 될까요??
N개의 노드가 있다고 가정했을 때, N개의 노드를 하나하나 탐색을 진행하므로 O(N)의 복잡도를 가지는 것을 알 수 있습니다.
DP 알고리즘을 이용하면 훨씬 더 빠르게 LCA를 찾을 수 있습니다. 하나 하나 부모를 찾아서 올라가는 것이 아니라 2^K 꼴로 부모를 찾아서 이동을 진행 합니다.
-
DP[노드번호] [K]
: 해당 노드의 2^K번 째 부모 노드
DP배열의 정의는 다음과 같습니다. DP배열을 이용하면 어떻게 탐색 횟수를 줄일 수 있는지 아래 예시를 통해서 보겠습니다.
똑같이 2번 노드와 9번 노드의 공통 조상을 찾겠습니다.
먼저, 2번 노드와 9번 노드의 깊이가 같아질때까지 9번 노드의 부모를 탐색해서 올려보겠습니다.
1) 2번 노드와 9번 노드 비교
9번 노드가 깊이가 더 깊고, DP[9] [2] = 5번 노드는 2번 노드랑 깊이 얕으므로 넘어가고, DP[9] [1] = 8번 노드는 2번 노드보다 깊이가 깊으므로 9번 노드를 한 번에 8번 노드로 올려줍니다.
2) 2번 노드와 8번 노드 비교
8번 노드가 깊이가 더 깊고, Dp[8] [1] = 5번 노드는 2번 노드보다 깊이가 얕으므로 넘어가고, Dp[8] [0] = 3번 노드는 2번 노드와 깊이가 같으므로 8번 노드를 3번 노드로 옮겨줍니다.
3) 2번 노드와 3번 노드 비교
DP[2] [1] = DP[3] [1] = 1번 노드이므로 1번 노드는 공통 조상입니다.
DP[2] [0] = DP[3] [0] = 5번 노드이므로 5번 노드도 공통 조상입니다.
따라서, 가장 가까운 공통 조상은 5번 노드가 됩니다.
이치럼 DP를 이용한 LCA 알고리즘은 2^K 꼴로 부모를 찾아서 이동하므로 그래프 탐색을 이용한 알고리즘보다 훨씬 효율적입니다.
먼저, DP배열과 깊이를 담고 있는 Depth 배열이 필요합니다.
// set(root노드번호, 0);
void set(int cur, int parent) {
// 현재 높이는 부모 높이 + 1
depth[cur] = depth[parent] + 1;
// 나중에 사용하기 위해 가장 높은 높이를 따로 저장
maxDepth = max(maxDepth, depth[cur]);
// dp[cur][0] = cur의 2^0번 째 부모이므로 바로 위 부모를 의미
dp[cur][0] = parent;
int length = depth[cur] - 1, k = 1, powK = 2;
while (powK <= length) {
// dp[cur][K] 는 cur의 2^K번 째 부모
// 따라서 cur의 2^(k - 1)번 째 부모의 2^(k - 1)번 째 부모랑 동일
dp[cur][k] = dp[dp[cur][k - 1]][k - 1];
k++;
powK *= 2;
}
// 자식 노드로 재귀적으로 진행
for (int next : graph[cur]) {
if (depth[next]) continue;
set(next, cur);
}
}root노드번호부터 시작해서 재귀적으로 구할 수 있습니다.
dp[cur] [k] := dp[ dp[cur] [k - 1] ] [ k - 1] 이 성립하므로 DP 배열을 채울 수 있습니다.
이제 필요한 셋팅을 다 진행했으므로 공통 조상을 구하면 됩니다.
// maxLevel은 Dp[i][k] 에서 K에 들어갈 수 있는 최대값을 의미합니다.
// maxDepth를 따로 구해놓았으므로 maxLevel은 log2 함수를 이용해 쉽게 구할 수 있습니다.
// maxLevel = (int)floor(log2(maxDepth - 1));
int LCA(int x, int y) {
// 먼저 높이가 더 높은 노드를 올려서 높이를 맞추자
if (depth[x] != depth[y]) {
if (depth[x] < depth[y])
swap(x, y);
// x를 y랑 같은 높이까지 올려주자
for (int i = maxLevel; i >= 0; i--)
if (depth[y] <= depth[dp[x][i]]) {
x = dp[x][i];
}
}
// 같은 높이에서 공통 조상을 계속 찾아보자.
int res = x;
if (x != y) {
for (int i = maxLevel; i >= 0; i--) {
if (dp[x][i] != dp[y][i]) {
x = dp[x][i];
y = dp[y][i];
}
res = dp[x][i];
}
}
return res;
}
DP 알고리즘을 이용해서 O(N)의 복잡도를 O(logN) 으로 줄일 수 있습니다.