백준 11437 : LCA

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

11437번: LCA

 

트리를 만들고 최소 공통 조상을 찾는 문제다.

LCA 알고리즘이 사용되는 문제고, 입력받은 edge를 순회하면서 트리를 만들고 각 노드의 height(라고 코드에서 사용했지만 depth가 맞는 표현같다.)와 parent값을 저장해준 후 검사하고자 하는 노드를 부모노드로 한 칸씩 이동시키면서 확인하면 된다.

 

#include <iostream>
#include <vector>
#include <queue>

using namespace std;

int n;
vector<int> edge[50'001];
int height[50'001];
int parent[50'001];

void make_tree() {
	int cur, next;
    //q에 height값을 넣어주어 관리해도 되지만
    //각 height를 시작할 때 q 사이즈를 확인하는 식으로도 height를 체크할 수 있다.
	int cur_height = 0, cur_height_size = 0;
	queue<int> q;
	q.push(1);
	parent[1] = 1;
	
	while (!q.empty()) {
    	//현재 높이를 전부 순회한 경우 height 증가 및 현재 height의 노드 수 저장
		if (cur_height_size <= 0) {
			cur_height_size = q.size();
			++cur_height;
		}
		cur = q.front();
		q.pop();

		for (int i = 0; i < edge[cur].size(); i++) {
			next = edge[cur][i];
			if (parent[next]) continue;

			parent[next] = cur;
			height[next] = cur_height;
			q.push(next);
		}

		--cur_height_size;
	}
}

int LCA(int a, int b) {
	if (height[a] > height[b]) {
		int tmp = a;
		a = b, b = tmp;
	}
    
    //높이가 같아질때까지 깊이가 깊은 노드를 부모노드로 이동시킴
	while (height[a] != height[b])
		b = parent[b];

	//현재 노드가 같은 값인지 확인
    //아니라면 두 노드를 각각 부모노드로 이동시킴
	while (a != b) {
		a = parent[a];
		b = parent[b];
	}

	return a;
}

void solution() {
	int m;
	int a, b;
	cin >> n;
	for (int i = 1; i < n; i++) {
		cin >> a >> b;
		edge[a].push_back(b);
		edge[b].push_back(a);
	}

	make_tree();

	cin >> m;
	while (m--) {
		cin >> a >> b;
		cout << LCA(a, b) << '\n';
	}
}

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

	return 0;
}

메모리: 5304 kb

시간: 840 ms

 

근데... 위의 방법으로 구현하면 노드의 수 N, 쿼리의 수 M일때, 각 쿼리에 대하여 O(N)의 시간복잡도를 갖는데,

사실 LCA알고리즘은 O(logN)의 시간복잡도로도 구현할 수 있다.

O(logN)풀이는 아래 링크를 참고하도록 하자.

https://unfunhy.tistory.com/114

백준 11438 : LCA 2

O(logN)풀이

메모리: 8428 kb

시간: 36 ms