LCA는 트리를 이용해서 최단거리 알고리즘을 구하는 것이다.
최소 공통조상을 구하는 알고리즘이다. Lowest Common Ancestor
구현
0. dfs or bfs depth , parent[N][K] : N번 노드의 2^K번째 조상 기록
parent[2][0] = 2번 노드의 첫번째 조상
parent[2][1] = 2번 노드의 두번째 조상
parent[2][2] = 2번 노드의 네번째(2^2) 조상
dfs로 구현하면 stack이 터질 수 있으니, bfs로 구현하는 것이 좋다.
2^K번째 조상을 기록 한다는것이 잘 이해가 안갈 수 있다. 왜 2^K번째 조상을 기록할까? 시간복잡도를 줄이기 위해서이다.
다음을 보자. 1에서 12로 이동할때
이진법으로 움직이면?
1->2->-3->4->5->6->7->8->9->10 ->11 ->12 : 한칸씩 뛰면 11번 이동, 비효율적임
1--------(2^3)---------->9-----(2^1)---->11-(2^0)->12 : 2진법으로 움직이면 3번 이동, 효율적임
규칙을보면 다음과 같은 점화식을 얻을 수 있다.
parent[N][K] = parent[parent[N][K-1]][K-1];
A ------------> C parent[A][4] = C
1 17
A ----- B ----> C parent[A][3] = B , parent[B][3] = C
1 9 17 parent[A][4] = parent[parent[A][3]][3]
1. LCA 로직
1) 양쪽 노드중 깊이가 깊은 것을 끌어올려 깊이를 맞춘다.( 2진법으로 뛸 수 있는 만큼 높이 뛰기)
2) if(a == b) return a;
3) else 높이가 맞춰진 양쪽 노드를 동시에 끌어올린다.
단 2진법으로 뛸수 있는만큼 뛰는데, ***부모가 다를경우에만 점프
4) return parent[a][0]; // a또는 b의 부모
샘플코드
BFS
static int MAX =18;
static int[] depth = new int[MAX];
static int[][] parent = new int[MAX][32];
// 2^k = N -> k = logN : parent배열의 열의 사이즈는 logN
// 2^10 = 10^3 , 2^40 = 2^10^4 = 10^3^4 = 10^12
// 2^17 = 13만 , 2^18 = 26만 , 2^20 = 104만
static boolean[] visited = new boolean[MAX];
static ArrayList<Integer>[] adj = new ArrayList[MAX];
static void bfs(int now) {
Queue<Integer> q = new ArrayDeque<>();
q.add(now);
while (!q.isEmpty()) {
now = q.poll();
visited[now] = true;
for (int next : adj[now]) {
if (visited[next]) continue;
parent[next][0] = now;
for (int j = 1; j < MAX; j++) {
parent[next][j] = parent[parent[next][j - 1]][j - 1];
}
depth[next] = depth[now] + 1; //// next의 depth는 현재의 depth++;
q.add(next);
}
}
}
LCA
static int LCA(int a, int b) {
// detph 맞추기
// 0. 항상 a보다 b가 아래에 있는 상태로 만들어주기
if (depth[a] > depth[b]) {
int tmp = a;
a = b;
b = tmp;
}
//1. 양쪽 노드의 깊이를 맞춰주기 (B를 A가 있는 depth까지 끌어올리기)
// 1 ---------->12 몇층 이동할까?
// 12---->4-->2->1
for (int i = MAX-1; i >= 0; i--) {
if (depth[b] - depth[a] >= (1 << i)) { // 2^i : 이동할 수 있는만큼 이동하기
b = parent[b][i];
}
}
// 2. a,b 높이가 맞춰진 상태 - 현재 위치가 LCA인 경우?
if (a == b) { return a; }
//3. 양쪽을 동시에 2진법으로 끌어올릴수 있는 만큼 끌어올리는데,단 부모가 다르면 이동
for (int i = MAX-1; i >= 0; i--) {
if (parent[a][i] != parent[b][i]) { //부모가 다르면 이동
a = parent[a][i];
b = parent[b][i];
}
}
return parent[a][0];
}