LCA

(이 내용은 제가 이해한 걸 정리해둔 거라 틀린 내용이 있을 수도 있습니다.)

 

LCA는 Lowest Common Ancestor로 트리에서 두 노드가 있을 때 두 노드의 최소 공통 조상을 찾는 알고리즘이다.

 

각 노드에 깊이가 있을 때(루트 노드=$1$, 루트 노드의 자식들=$2,3,...$)

(1) 두 노드의 깊이를 맞춰준 후

      $(depth_u=3, depth_v=5$ 이면 $\rightarrow$ $depth_u=depth_v=3)$

(2) $u=v$일 때까지 부모 노드로 계속 올라간다.

 

(1), (2)를 수행하는 과정에서 한쪽으로 치우쳐진 $n$개의 노드를 가진 트리이면 시간 복잡도가 $O(n)$이 된다.

LCA를 구하는 쿼리가 $m$개 들어오면 $O(nm)$이라서 문제를 풀 때 시간 초과가 되는데

이를 DP를 사용해서 $O(log(n))$만에 구할 수 있다.

 

한 단계씩 올라가면서 찾는 게 아니라 $2^x$씩 올라가면서 찾으면 한 쿼리당 시간 복잡도가 $O(log(n))$이 되고, $m$개의 쿼리를 처리하는데 $O(mlog(n))$의 시간이 된다. (+세그먼트 트리를 사용한 방법도 있는데 나중에 추가할 예정)

점화식을 $par_{x,i}$ : $x$노드의 $2^i (i\geq0)$번째 조상이라고 하면 $par_{x,i}=par_{par_{x,i-1},i-1}$ : $(x$의 $2^{i-1}$번째 조상$)$의 $2^{i-1}$의 조상이라 하면 된다.$(i\geq1)$

이런 방식으로 조상을 저장해두고 이를 참고해서 빠르게 올라가는 방법을 sparse table이라 한다.

 

(예시) $3, 6$노드의 LCA를 구하는 과정

 

(1) 두 노드의 깊이를 맞춰준다.

$depth_6=4$, $depth_3=2$, 깊이가 다르므로 $6$번 노드의 깊이가 $3$번 노드의 깊이와 같게 해준다. $6$번 노드에서 $par_{6,i}$ ($i : max\_height \rightarrow 0$)의 깊이를 보면서 $depth_x\geq depth_3$의 조건을 만족하는 $x$로 이동하고 이를 반복한다.

여기서 $max\_height$의 최대값은 $\lfloor log(n)\rfloor$이다. (한쪽으로 쏠린 편향 트리의 노드가 $n$일 때 바닥에서 $2^{\lfloor log(n)\rfloor}$만큼 올라가야 루트 노드가 되기 때문에)

이 작업을 $O(log(n))$에 할 수 있다.

 

 

(2) $u=v$일 때까지 부모 노드로 계속 올라간다.

두 노드의 높이가 같아 졌다면 (1)의 작업과 비슷하게 $x$($3$과 깊이가 같아진 노드, 위의 예제에선 $2$)와 $3$에 대하여  $par_{x,i} = par_{3,i}$, ($i : max\_height \rightarrow 0$)의 조건을 만족하는 노드로 이동하고 이를 반복하여 LCA를 구할 수 있다.

 

BOJ 11437 (LCA)

코드 :

<hide/>
#include<iostream>
#include<vector>
#include<cmath>
#include<algorithm>
using namespace std;

const int N = 50000;
vector<int> adj[N + 2];
int height[N + 2];
int par[N + 2][16];
int max_height = 15;

void make_tree(int x, int parent) {

	height[x] = height[parent] + 1;
	par[x][0] = parent;

	for (int i = 1; i <= max_height; i++) {
		par[x][i] = par[par[x][i - 1]][i - 1];
	}
	for (auto it : adj[x]) {
		if (it == parent) continue;
		make_tree(it, x);
	}
	return;
}

int lca_query(int a, int b) {
	if (height[a] != height[b]) {
		if (height[a] > height[b]) swap(a, b);
		for (int i = max_height; i >= 0; i--) {
			if (height[a] <= height[par[b][i]]) b = par[b][i];
		}
	}
	int lca = a;
	if (a != b) {
		for (int i = max_height; i >= 0; i--) {
			if (par[a][i] != par[b][i]) {
				a = par[a][i];
				b = par[b][i];
			}
			lca = par[a][i];
		}
	}
	return lca;
}

int main() {
	int n, m;
	cin >> n;
	for (int i = 1; i < n; i++) {
		int x, y;
		cin >> x >> y;
		adj[x].push_back(y);
		adj[y].push_back(x);
	}

	make_tree(1, 0);

	for (cin >> m; m--;) {
		int x, y;
		cin >> x >> y;
		cout << lca_query(x, y) << '\n';
	}
	return 0;
}

 

(BOJ에서 11437, 11438, 1761, 3176, 13511을 풀면서 공부한 내용입니다.)