[PS] LCA 2 / C++ (백준 11438번)

LCA 2 (백준 11438번)

 

희소 배열(Sparse Table)을 사용해 LCA를 O($logn$)만에 구해야한다. 일반적으로 희소 배열을 사용하면 O(n)이 걸리기 때문에 Binary Lifting 방식으로 공통 조상을 찾는 과정이 필요하다.

 

풀이 과정

1. 우선 dfs()함수로 트리를 만들며 각 node들의 parent 정보를 희소 배열에 저장하는데 이때, 희소 배열을 2차원으로 parent[i][j]=i번째 node에서 $2^j$번째 부모를 저장하는 방식으로 만들어준다. N<=100,000이었기 때문에 2의 거듭제곱으로 17까지면 충분하지만 관례적으로 18이상으로 안전 여유를 둔다.

 

2. depth 배열을 만들어 각 node들의 깊이 또한 저장해준다. 주요 식은 다음과 같다.

parent[i][j]=parent[parent[i][j-1]][j-1];

 

3. 다음 입력받은 두 노드의 깊이를 맞춰준다. 이때, 2의 거듭제곱으로 큰 값부터 작은 값으로($2^{18}$~$2^0$) 줄어들며 깊이를 맞춘다.

 

4. a와 b가 같은 깊이에 있지만 다른 node를 가진다면 위 방식과 똑같이  큰 값부터 작은 값으로 줄어들며 부모 조상을 비교하는데 이때 부모가 달라진다면 a, b를 갱신시킨다. 처음 갱신 시에 공통 부모 조상의 2의 거듭제곱 바로 전 단계에서 갱신이 되며, 목표값과 차이는 작아지는 i값만으로도 충분하기 때문에 다음과 같은 LCA() 함수로 구현된다. (글 해석보다 코드 해석이 빠를듯..)

Binary Lifting을 이용한 개선된 최소 공통 조상(Lowest Common Ancestor) 구하는 방법 배우기2

이 과정은 위 게시물에서 귀납법으로 증명을 잘 해주셨다.

 

#include<iostream>
#include<algorithm>
#include<vector>
using namespace std;

vector<int> vec[100001];
int parent[100001][21];
int depth[100001], vi[100001];

void dfs(int node, int _depth) {
	vi[node] = 1;
	int size = vec[node].size();
	for (int i = 0; i < size; i++) {
		int next_node= vec[node][i];
		if (vi[next_node] == 0) {
			parent[next_node][0] = node;
			depth[next_node] = _depth + 1;
			dfs(next_node, _depth + 1);
		}
	}
	return;
}

int LCA(int a, int b) {
	if (depth[a] < depth[b])swap(a, b);

	for (int i = 18; i >= 0; i--) {
		if (depth[a] - depth[b] >= (1 << i))
			a = parent[a][i];
	}

	if (a == b)return a;

	for (int i = 18; i >= 0; i--) {
		if (parent[a][i] != parent[b][i]) {
			a = parent[a][i];
			b = parent[b][i];
		}
	}

	return parent[a][0];
}

int main()
{
	int n, m;
	scanf("%d", &n);
	for (int i = 1; i < n; i++) {
		int a, b;
		scanf("%d %d", &a, &b);
		vec[a].push_back(b);
		vec[b].push_back(a);
	}

	dfs(1, 0);

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

	scanf("%d", &m);
	for (int i = 1; i <= m; i++) {
		int a, b;
		scanf("%d %d", &a, &b);
		printf("%d\n", LCA(a, b));
	}
	return 0;
}