[알고리즘] 최소 공통 조상 - LCA(Lowest Common Acestor)
1. LCA (Lowest Common Acestor) 알고리즘이란?
트리 구조에서 최소 공통 조상을 찾는 알고리즘으로, 두 정점 (u, v)에서 가장 가까운 공통 조상을 찾는 알고리즘입니다.
아래와 같은 트리가 있다고 해보겠습니다.
(u, v)의 조상을 LCA(u, v)라고 하면, LCA(2, 7)은 무엇일까요? 🤔
몇 번 더해보겠습니다. LCA(9, 6)은 무엇일까요?
마지막으로, LCA(12, 14)는 무엇일까요?
LCA(12, 14) = LCA(14, 12) = 12 라는걸 알 수 있습니다. 최소 공통 조상이라는게 무엇인지 이해되셨나요? 🙂
2. LCA 알고리즘 동작 과정
우선 가장 먼저 해야할 건 당연히 입력받은 정점과 간선으로 트리를 구성하는 것입니다.
다음으로, depth와 조상 노드를 같이 구해야 하는데 이때, 조상 노드는 2^K 번 째의 모든 조상 노드를 구합니다.
2^0번째 조상 노드는 자기 바로 위의 부모 노드이고, 2^1번째는 자기 부모의 부모 노드가 된다.
3. 코드
트리를 만들었다면, 각 노드의 2^K 번 째 조상 노드를 depth[] 배열에 담아둡니다.
그런 다음, LCA(a, b)에 대해 depth를 맞춘 후, 둘의 공통 조상을 구합니다.
class Main {
// ...생략
private static int lca(int a, int b) {
if (depth[a] < depth[b]) { // 깊이가 낮은 쪽을 기준으로 맞춘다.
int temp = a;
a = b;
b = temp;
}
//더 깊은 a를 2승씩 점프하며 두 노드의 depth를 맞춘 후, 맞춘 depth의 조상 노드로 대체한다.
for (int i = K - 1; i >= 0; i--) {
if (Math.pow(2, i) <= depth[a] - depth[b]) {
a = parents[a][i]; // a를 2^i 번 째 조상 노드로 대체한다.
}
}
// depth 맞춘 후 대체한 조상 노드가 b와 같다면. 즉, a의 조상노드가 b라면 종료한다.
if (a == b) return a;
// 이제 두 노드는 같은 depth를 가지기 때문에
// 같이 2승씩 점프시키며 공통부모 바로 아래까지 올린다.
for (int i = K - 1; i >= 0; i--) {
if (parents[a][i] != parents[b][i]) {
a = parents[a][i];
b = parents[b][i];
}
}
return parents[a][0];
}
private static void fillParents() {
for (int i = 1; i < K; i++) {
for (int j = 1; j <= N; j++) {
parents[j][i] = parents[ parents[j][i - 1] ][i - 1];
}
}
}
private static void dfs(int from, int cnt) {
depth[from] = cnt++;
for (Integer next : tree.get(from) {
if (depth[next] == 0) {
dfs(next, cnt);
parents[next][0] = from;
}
}
}
}
4. 참고자료
[1] https://www.crocus.co.kr/660
'Algorithm > Theory' 카테고리의 다른 글
[알고리즘] 수열의 순열과 조합 (0) | 2020.09.26 |
---|---|
[알고리즘] LCS(Longest Common Subsequence) (0) | 2020.09.13 |
[알고리즘] 최소비용 신장트리(MST) - Prim 알고리즘 (0) | 2020.09.07 |
[알고리즘] 최단 경로 (0) | 2020.08.24 |
[자료구조] B-트리 (0) | 2020.02.13 |
댓글
이 글 공유하기
다른 글
-
[알고리즘] 수열의 순열과 조합
[알고리즘] 수열의 순열과 조합
2020.09.26 -
[알고리즘] LCS(Longest Common Subsequence)
[알고리즘] LCS(Longest Common Subsequence)
2020.09.13 -
[알고리즘] 최소비용 신장트리(MST) - Prim 알고리즘
[알고리즘] 최소비용 신장트리(MST) - Prim 알고리즘
2020.09.07 -
[알고리즘] 최단 경로
[알고리즘] 최단 경로
2020.08.24