LCA 알고리즘이란,
트리 상의 정점 U 와 V 가 주어질 때 U 와 V 에서 가장 가까운 공통 조상을 찾는 알고리즘이다.
위 LCA 그래프 예시에서 24 와 26 의 LCA (최초 조상) 은 5 이다.
어떻게 조상을 찾는 것일까?
조상을 찾는 방법을 step-by-step 으로 표현한다면 다음과 같다.
0 . U 노드와 V 노드를 정한다. (깊이가 더 큰 노드를 V로 정한다.)
1 . U 노드의 깊이와 V 노드의 깊이가 같아질 때까지 깊이가 더 깊은 노드(V)를 자신의 조상으로 바꾸어 준다.
2 . U 노드와 V 노드의 조상이 같아질 때까지 자신의 조상으로 바꾸어 준다.
1 번 과정, 2 번 과정 모두 한 단계씩 조상을 올리게 되면 O(N) (깊이를 N이라 두었을 때) 의 복잡도를 가지게 된다.
조금 더 빠르게 트리를 탐색하기 위해 $2^{x}$ 번째에 해당하는 부모만 기억하고 중학교 때 배운 아래 지수법칙
$2^{x+1}=2^{x}*2$ 수식을 활용한다. 수식에서 * 2 부분을 만족하려면 조상노드를 한 번 더 그 크기만큼 올라가야 한다.
따라서,
u 노드의 $2^{x}$ 번째에 해당하는 부모를 parent[u][x] 라고 할 때, parent[u][x] = parent[parent[u][x-1]][x-1] 라는 점화식이 성립한다. 점화식이 만들어졌으니 Bottom-Up DP 로 parent 테이블을 만들어주면 된다.
총 루틴 정리
알고리즘의 중요 부분은 모두 나왔다. 총 루틴을 정리해보자.
1 . 그래프의 깊이를 구한다.
이 LCA 에서 사용하는 트리는 이진 트리이므로 높이는 log2(N) + 1이다. 여기서 N은 총 그래프 노드의 개수.
(int)Math.ceil(Math.log(n)/Math.log(2)) +1;
2 . DFS 로 순회하면서 depth 배열과 parent[][0] 배열을 초기화한다.
3 . parent[x][y] 배열을 셋팅한다.
parent[x][y] = parent[parent[x][y-1]][y-1] 점화식이 성립하고 미래 값을 먼저 구하지 않아도 되므로 Bottom-up DP 로 구할 수 있다.
4 . LCA(a, b) 에서 b 가 더 깊도록 a 와 b 를 서로 바꾼다.
5 . b 깊이가 a 깊이와 같도록 부모 배열을 활용해 자신의 조상으로 바꾼다.
6 . 현재 부모가 같다면 리턴.
7 . 조상이 같을 때까지 조상을 거슬러 올라가기. 부모가 같다면 그 조상을 리턴.
자바 코드
자바코드는 다음과 같다.
public static class LCA {
private int nodeCount;
private List<Integer>[] adjacencyList;
private int treeHigh;
private int[] depth;
private boolean[] memoization;
private int[][] parent;
public LCA(int nodeCount, List<Integer>[] adjacencyList) {
this.nodeCount = nodeCount;
this.adjacencyList = adjacencyList;
this.memoization = new boolean[nodeCount+1];
this.depth = new int[nodeCount+1];
getTreeHigh();
this.parent = new int[nodeCount+1][this.treeHigh];
}
private void getTreeHigh() {
this.treeHigh = (int)Math.ceil(Math.log(nodeCount)/Math.log(2)) + 1;
}
private void init(int current, int treeHigh) {
memoization[current] = true;
depth[current] = treeHigh;
for (int next : adjacencyList[current]) {
// 메모이제이션
if(memoization[next]) continue;
init(next, treeHigh+1);
parent[next][0] = current;
}
}
private void makeParentArray() {
for(int i=1; i<treeHigh; i++) {
for(int j=1; j<nodeCount+1; j++) {
parent[j][i] = parent[parent[j][i-1]][i-1];
}
}
}
public int run(int a, int b) {
init(1,1);
makeParentArray();
// b 가 더 깊도록 설정
if (depth[a] > depth[b]) {
int temp = a;
a = b;
b = temp;
}
// 깊이가 동일하도록 b 를 옮김
for (int i = treeHigh-1; i>=0; i--) {
if ((1<<i) <= depth[b] - depth[a]) {
b = parent[b][i];
}
}
if(a==b) return a;
for(int i=treeHigh-1; i>=0; i--) {
if (parent[a][i] != parent[b][i]) {
a = parent[a][i];
b = parent[b][i];
}
}
return parent[a][0];
}
}
'알고리즘 > 개념' 카테고리의 다른 글
| [알고리즘] Segment Tree (0) | 2022.08.29 |
|---|---|
| [알고리즘] BFS & DFS (0) | 2022.07.12 |
| [알고리즘] 투 포인터 알고리즘 (Two Pointer) (0) | 2022.06.29 |
| [알고리즘] DP (Dynamic Programming) (0) | 2021.05.10 |
