백준 - LCA(11437)

새로운 알고리즘이다.

최소 공통 조상을 찾아주어야 한다.

 

 

해당 트리를 예시로 든다.

1은 루트 노드이다.

 

10과 15노드의 최소 공통 조상은 2이다.

루트노드로 계속 거슬러 올라가며 공통으로 도달하는 노드이다.

 

 

10과 15의 레벨을 확인해준다.

루트노드가 레벨이 1부터 시작하면

10은 4이고 15는 5이다.

 

레벨이 같아질 때까지 노드를 이동해 준 다음

동시에 한 레벨씩 올라가면 LCA를 찾을 수 있다.

 

 

 

 

//11437 LCA
#include <iostream>
#include <vector>
using namespace std;
vector<vector<int>> adj;
vector<int> level;
vector<int> parent;
int n;

int lca(int a, int b) {
	if (level[a] < level[b]) swap(a, b);

	while (level[a] != level[b]) a = parent[a];

	while (a != b) {
		a = parent[a];
		b = parent[b];
	}
	return a;
}


void set_tree(int node, int p_node) {
	parent[node] = p_node;
	level[node] = level[p_node] + 1;

	for (int i = 0; i < adj[node].size(); i++) {
		int child = adj[node][i];
		if (child == p_node) continue;
		set_tree(child, node);
		
	}
}

int main()
{
	cin >> n;
	adj.assign(n + 1, {});
	level.assign(n + 1, 0);
	parent.assign(n + 1, 0);

	for (int i = 1; i < n; i++) {
		int a, b;
		cin >> a >> b;
		adj[a].push_back(b);
		adj[b].push_back(a);
	}
	set_tree(1, 0);

	int k;
	cin >> k;
	for (int i = 0; i < k; i++) {
		int x, y;
		cin >> x >> y;
		cout << lca(x, y) << endl;
	}

}

전체 코드이다.

 

 

void set_tree(int node, int p_node) {
	parent[node] = p_node;
	level[node] = level[p_node] + 1;

	for (int i = 0; i < adj[node].size(); i++) {
		int child = adj[node][i];
		if (child == p_node) continue;
		set_tree(child, node);
		
	}
}

이 부분에서 레벨 정보와 부모노드 정보를 입력해 준다.

 

 

 

int lca(int a, int b) {
	if (level[a] < level[b]) swap(a, b);

	while (level[a] != level[b]) a = parent[a];

	while (a != b) {
		a = parent[a];
		b = parent[b];
	}
	return a;
}

a를 항상 큰 레벨로 만들어주고

a와 b가 레벨이 같아질 때까지

a레벨을 상승시켜 준다.

 

그 후 두 개의 노드의 부모가 같아질 때까지 계속 상승해 준다.