BOJ : 11438 LCA 2

---

[BOJ 11438(P5)리뷰]

트리에서 두개의 정점이 주어졌을 때, 두 정점의 최소공통조상을 찾아야 한다.

최소 공통조상 이란 두개의 노드가 만나게 되는 부모 노드 중 가장 가까운 것을 말한다.

아래의 과정을 통해 구할 수 있다.

• dfs를 통해 모든 정점의 깊이를 기록하며 이때 자신의 위에있는 부모노드의 번호를 저장한다.
• 두개의 정점을 입력받고, 두 정점의 깊이를 맞춘다.
• 같아진 깊이로부터 위로 올라간다. 이 때, 만약 서로 같은 노드를 만나게되면 그게 최소공통조상이다.

LCA 문제는 위 과정을 코드로 구현하면 풀 수 있으나 이 문제는 이방법으로는 풀 수 없다.

왜냐하면, 노드의 개수와 명령의 개수가 최대 10만개이므로 만약 리프노드에서 루트노드까지 찾는과정을 반복해야 한다면 시간초과가 날 수밖에없다.

따라서 이 문제를 해결하기 위해서는 sparse table이라는 개념을 이용해야 한다.

sparse table에 대해 나는 이 블로그를 참고했다. 간략하게 설명하자면 sparse table은 2^0, 2^1, 2^2 꼴로 부모노드를 저장할 수 있게 해준다. 기존 코드는 자신의 1단계 위에 있는 부모노드만 저장했지만 sparse table을 이용하여 자신의 2^0번째, 2^1번째 ~ 2^17번째 부모노드까지 저장할 수 있게한다.

2^17까지 저장하는 이유는 최대 노드의개수가 10만개이므로, 모든 노드를 저장하기 위함이다. 2^17은 대략 13만정도 된다.

sparse table을 이용하는 장점은 기존에 깊이를 맞추기 위해, 공통조상을 찾기위해 자신의 위에있는 부모노드로 한칸씩 거슬러 올라갔지만, sparse table을 이용해 2^0 ~ 2^17 만큼 뛰어 이동할 수 있다.

만약 13계단을 올라갈떄, 1칸씩 13계단을 올라가면 13번 올라가야하지만, 8칸을 올라가고, 4칸을 올라가고, 1칸을 올라가면 3번만에 올라갈 수 있다는 차이와 같은 개념이다.

이 개념을 이용하여, 두개의 정점의 최소공통조상 바로 아래에 있는 노드까지 이동한 다음, 자신의 위에있는 노드를 반환하면 올바른 결과를 받을 수 있다.

/*
	21.01.19
	BOJ : 11438 LCA2 (https://www.acmicpc.net/problem/11438)
	최소공통조상
*/
#include <bits/stdc++.h>
using namespace std;

int N, M;
int depth[100001], an[100001][18];
vector <int> adj[100001];
bool vis[100001];

void dfs(int parent, int cur, int paramDepth) {
	if (vis[cur]) return;
	vis[cur] = true;
	depth[cur] = paramDepth;
	an[cur][0] = parent;
	for (int i = 0; i < adj[cur].size(); i++) {
		dfs(cur, adj[cur][i], paramDepth + 1);
	}
}

int LCA(int a, int b) {
	//깊이가 서로 다르면 맞춰준다.

	if (depth[a] < depth[b]) { //a의 깊이가 b보다 더 깊게 만들어서 쉽게 처리하기 위함.
		int tmp = a;
		a = b;
		b = tmp;
	}

	if (depth[a] != depth[b]) {
		// a의깊이가 b의 깊이와 같아질 때 까지 맞춘다.
		int diff = depth[a] - depth[b];
		for (int i = 0; i <= 17; i++) {
			if (diff & (1 << i)) {
				a = an[a][i];
			}
		}
	}

	//depth[a] == depth[b] && a == b면 그게 공통조상임.
	if (a == b) return a;

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

	//LCA의 바로 아래까지옴.
	return an[a][0];
}

int main() {
	cin.tie(0);
	ios::sync_with_stdio(0);

	cin >> N;
	for (int i = 0; i < N - 1; i++) {
		int a, b;
		cin >> a >> b;
		//일단 양방향으로 연결
		adj[a].push_back(b);
		adj[b].push_back(a);
	}

	//LCA를 위한 자료 수집 : 각 노드에 대한 깊이
	dfs(1, 1, 1);

	//2^1, 2^2, 2^3 ... 조상 set
	for (int i = 1; i <= 17; i++) { // 2^i번째 조상.
		for (int j = 1; j <= N; j++) { //1번 노드부터 N번 노드 까지
			int tmp = an[j][i - 1];
			an[j][i] = an[tmp][i - 1];
		}
	}

	cin >> M;
	for (int i = 0; i < M; i++) {
		int a, b;
		cin >> a >> b;
		cout << LCA(a, b) << '\n';
	}
	return 0;
}