[백준][11438][C++] LCA 2

링크

https://www.acmicpc.net/problem/11438

11438번: LCA 2

해설

이 문제는 DFS와 BFS 모두 사용할 수 있습니다.

그러나 BFS 가 메모리도 적게사용하고 시간도 약간 더 빨라 해설에서는 BFS를 사용하였습니다.

DFS버전이 궁금하시면 >> 깃허브 << 에 올려두었습니다.

 

 

골드문제에서는 주로 정적배열만으로 해결이 다 됬었는데 플레티넘으로 넘어가니 동적배열을 사용해야하네요.

2차원 vector 을 이용해서 각 노드별로 연결된 노드들의 숫자를 다 입력해둡니다.

 

그 후 BFS 를 이용해서 각 노드들의 깊이(depth) 를 구합니다.

 

골드문제인 11437 LCA 는 그냥 깊이를 맞추고 상승시켜가면서 같은걸 찾으면 되지만

이 문제같은 경우는 훨씬 노드가 많기때문에 O(N) 의 복잡도를 이용하면 시간초과가 나게됩니다.

보통 O(N) 보다 더 낮은 시간복잡도를 가지려면 이분탐색을 이용하는데 여기도 똑같습니다.

 

PARENT 배열에 각 노드의 2^0 , 2^1 , 2^2 , ... 위의 노드들을 저장해 두고 사용합니다.

이렇게 탐색을 하면 O(log N) 만에 찾을 수 있습니다.

 

코드를 보시면

PARENT[next][i] = PARENT[PARENT[next][i - 1]][i - 1]

위와 같은 코드를 보실 수 있는데

이코드의 의미는 현재 노드의 2^i 위의 부모는 2^(i - 1) 위 부모의 2^(i - 1) 위 부모와 같다는 뜻입니다.

그림과 같이 4 위의 노드는 2위의 노드의 2위 노드 와 같다는 것이죠.

그렇게 모든 2^i 위 노드들을 다 구해두고 입력이 들어올 때 마다 LCA 함수를 이용해서 값을 구해줍니다.

 

두 값의 깊이를 또 이분탐색을 이용해서 더 얕은것에 맞춰주고 아까 구해뒀던 PARENT 배열을 이용해

LCA 를 찾을 때 까지 이동을 하다가 찾으면 return 하면됩니다.

 

코드에 모두 구현되어있습니다.

 

코드

#include <iostream>
#include <vector>
#include <queue>
#include <algorithm>
using namespace std;
 
int N, M, DEP[100001], PARENT[100001][18];
bool visit[100001];
vector<vector<int>> LIST;
queue<int> que;
 
int LCA(int _a, int _b) {
	if (DEP[_a] < DEP[_b]) swap(_a, _b);
 
	int looper = 0;
	while (DEP[_a] != DEP[_b]) {
		++looper;
		if ((DEP[_a] - (1 << looper)) < DEP[_b]) {
			_a = PARENT[_a][looper - 1];
			looper = 0;
		}
	}
	while (_a != _b) {
		looper = 1;
		while (PARENT[_a][looper] != PARENT[_b][looper])
			++looper;
		_a = PARENT[_a][looper - 1];
		_b = PARENT[_b][looper - 1];
	}
	return _a;
}
 
void BFS() {
	que.push(1);
	while (!que.empty()) {
		int now = que.front();
		que.pop();
		for (int i = 0; i < LIST[now].size(); ++i) {
			int next = LIST[now][i];
			if (visit[next])
				continue;
			visit[next] = true;
			que.push(next);
			DEP[next] = DEP[now] + 1;
			PARENT[next][0] = now;
			for (int i = 1; i < 18; ++i) {
				PARENT[next][i] = PARENT[PARENT[next][i - 1]][i - 1];
			}
		}
	}
}
 
int main()
{
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);
 
	cin >> N;
	LIST.resize(N + 1);
	for (int i = 0; i < N - 1; ++i) {
		int a, b;
		cin >> a >> b;
		LIST[a].push_back(b);
		LIST[b].push_back(a);
	}
 
	DEP[1] = 1;
	visit[1] = true;
	BFS();
 
	cin >> M;
	for (int i = 0; i < M; ++i) {
		int a, b;
		cin >> a >> b;
		cout << LCA(a, b) << "\n";
	}
 
	return 0;
}