[BOJ] 백준 11437번: LCA

www.acmicpc.net/problem/11437

11437번: LCA

LCA는 최소 공통 조상 (Lowest Common Ancestor)로 두 노드를 잇는 가장 짧은 경로 중 깊이가 가장 얕은 노드입니다.

아래 트리에서 빨간 노드와 하늘색 노드의 LCA는 초록색 노드가 됩니다.

트리 예시

"트리 노드의 부모 노드는 유일하므로 루트를 향해 거슬러 올라가면서 가장 처음으로 공통된 노드를 찾자!" 아이디어를 기반으로 좀 더 빠르게 위로 올라갈 수 없을까 하는 고민이 생기게 됩니다.

효율적으로 부모 노드로 올라가기 위해 parent [i][j] 배열을 노드 j에서 2^i 번 거슬러 올라갔을 때 부모 노드로 정의해 봅시다.

위의 그림에서 parent [0][A]는 A의 2^0번 거슬러 올라갔을 때의 부모, 즉 A의 첫 번째 부모를 뜻하므로 parent [0][A] B가 되며, parent [1][A]는 A의 2^1번 거슬러 올라갔을 때의 부모, 즉 parent [1][A] = D가 됩니다.

또한 parent [i][j] = parent [i][parent [i-1][j]] 의 관계를 갖습니다. 

parent [1][A]는 A에서 2^1번 거슬러 올라간 부모의 노드임과 동시에, A에서 2^0번 거슬러 올라간 부모 B에서 2^0번 거슬러 올라간 노드로 생각할 수 있습니다.

이 관계를 기반으로 모든 노드 k의 parent [0][k]를 구하면 점화식을 통해 2^i 번 거슬러 올라간 부모 노드를 빠르게 구할 수 있습니다. 이를 코드로 나타내면 아래와 같습니다.

	for (int i = 1; i < 20; i++) {
		for (int j = 1; j <= n; j++) {
			parent[i][j] = parent[i-1][parent[i-1][j]];
		}
	}

 

 

아래 예시를 통해 빠르게 거슬러 올라가는 아이디어를 사용한 LCA 노드 찾는 알고리즘을 알아보겠습니다.

먼저 LCA노드는 두 노드가 처음으로 만나는 노드입니다. 만약 A와 B의 parent [i][A]와 parent [i][B]가 같다면 이 노드는 LCA노드이거나 LCA노드의 상위 노드일 것입니다. 

이러한 노드를 찾기 위해 먼저 노드 A와 B의 깊이가 같아질 때까지 더 깊은 노드를 끌어올려 주는 것이 필요합니다. 먼저 dfs를 통해 각 노드의 깊이와 첫 번째 부모 노드를 구할 수 있습니다.

void dfs(int node,int p) {
	parent[0][node] = p;
	depth[node] = depth[p] + 1;
	for (auto nxt : v[node]) {
		if (nxt != p) {
			dfs(nxt, node);
		}
	}
	return;
}

이렇게 구한 두 노드의 depth [A] - depth [B]의 차이 dif는 0 이상의 값을 갖습니다. (편의상 A노드가 더 깊은 노드라고 정의하겠습니다.) 위의 예시에서는 dif는 2가 됩니다.

이때 dif를 이진수로 나타내면 000.. 0010 이 되는데, 오른쪽에서 두 번째 비트가 켜있으므로 2^(2-1) 만큼 거슬러 올라가면 두 노드의 깊이가 같아진다는 것을 알 수 있습니다. 즉, dif의 비트 중 A를 parent [켜진 비트의 자리 -1][A] 만큼 거슬러 올라가면 최종적으로 A가 B의 깊이까지 거슬러 올라갈 수 있습니다.

만약 dif가 3 (00.. 011)인 경우 2^(2-1) -> 2^(1-1) 단계를 거슬러 올라가면 B노드와 깊이가 동일하게 됩니다.

이를 코드로 나타내면 아래와 같습니다.

	int da = depth[a];
	int db = depth[b];
	if (da < db) {
		swap(a, b);
	}
	da = depth[a];
	db = depth[b];
	int dif = da - db;
	for (int i = 19; i > -1; i--) {
		if (dif & (1 << i)) {
			a = parent[i][a];
		}
	}

이렇게 A와 B의 깊이를 맞춰주게 되면 두 가지 경우가 생기게 됩니다.

1. A`와 B가 같은 노드인 경우, 즉 LCA노드가 B인 경우

2. A`와 B가 다른 노드인 경우, 즉 A`노드와 B노드가 LCA노드의 하위 노드인 경우

첫 번째 경우에서는 B가 LCA이므로 더 이상 진행할 필요가 없습니다.

두 번째 경우에서는 A`노드와 B노드를 같은 깊이만큼 끌어올리면서 LCA 탐색합니다.

i를 큰 수에서 0까지 감소시키면서 parent [i][B]와 parent [i][A]가 다르면 A = parent [i][A], B = parent [i][B]로 끌어올려줍니다. 최종적으로 A`와 B`은 LCA를 부모로 같은 노드까지 올라오게 되며 LCA는 parent [0][A]로 구할 수 있습니다. 만약 parent [i][A]와 parent [i][B]가 같을 때 끌어올려주게 되면 해당 노드가 LCA의 노드인지 LCA 노드의 조상 노드인지 모르기 때문에 끌어올려주지 않습니다.

 

이 과정을 코드로 나타내면 아래와 같습니다.

	int LCA = a;
	if (a != b) {
		for (int i = 19; i > -1; i--) {
			if (parent[i][a] != -1 && parent[i][a] != parent[i][b]) {
				a = parent[i][a];
				b = parent[i][b];
			}
		}
		LCA = parent[0][a];
	}
	return LCA;

 

전체 코드는 아래와 같습니다. 

#include <algorithm>
#include <cstdio>
#include <vector>
#include <iostream>
#include <memory.h>

using namespace std;

int n;
vector<int> v[100001]; // 도착지, 경로 번호

int depth[100001];
int parent[100001][20];
int _size[100001];
int dfs(int node,int p) {
	_size[node] = 1;
	parent[node][0] = p;
	depth[node] = depth[p] + 1;
	for (auto nxt : v[node]) {
		if (nxt != p) {
			_size[node] += dfs(nxt, node);
		}
	}
	return _size[node];
}
int LCA(int a, int b) {
	int da = depth[a];
	int db = depth[b];
	if (da < db) {
		swap(a, b);
	}
	da = depth[a];
	db = depth[b];
	int dif = da - db;
	for (int i = 19; i > -1; i--) {
		if (dif & (1 << i)) {
			a = parent[a][i];
		}
	}
	if (a != b) {
		for (int i = 19; i > -1; i--) {
			if (parent[a][i] != -1 && parent[a][i] != parent[b][i]) {
				a = parent[a][i];
				b = parent[b][i];
			}
		}
		a = parent[a][0];
		b = parent[b][0];
	}
	return a;
}
int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(NULL), cout.tie(NULL);
	cin >> n;
	for (int i = 1; i < n; i++) {
		int a, b;
		cin >> a >> b;
		v[a].emplace_back(b);
		v[b].emplace_back(a);
	}
	memset(parent, -1, sizeof(parent));
	depth[0] = 1;
	dfs(1, 0);


	for (int i = 1; i < 20; i++) {
		for (int j = 1; j <= n; j++) {
			parent[j][i] = parent[parent[j][i-1]][i-1];
		}
	}
	int m;
	cin >> m;
	for (; m--;) {
		int a, b;
		cin >> a >> b;
		cout << LCA(a, b) << "\n";
	}
}

 

이 문제도 같이 풀어보세요

2020/07/05 - [알고리즘] - [BOJ] 백준 3176번: 도로 네트워크

[BOJ] 백준 3176번: 도로 네트워크