[알고리즘] 백준 3584번: 가장 가까운 공통 조상 (C++)

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

3584번: 가장 가까운 공통 조상

테스트 케이스마다 매번 루트 노드가 달라지기 때문에 트리가 만들어지기 전에 루트 노드를 먼저 찾아야 했다.

그래도 이번 문제에서는 a와 b가 주어졌을 때 부모-자식 관계가 명확했기 때문에 루트 노드를 찾는 함수를 만들 수 있었다.

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

입력을 받으면서 adj에 넣어줌과 동시에 b의 부모는 a다 라는 것을 알려주는 배열을 만들어주었다.

>> 나중에 트리 전처리할 때, parent 배열을 쓰긴 하지만 그냥 별개로 이해하기 쉽게 만들었다.

int rootNode = findRoot(n);

그다음 루트 노드를 알아내기 위해 루트 노드를 찾아내는 함수를 만들어주었고, n을 넣은 이유는 딱히 없다.

>> 어떤 노드를 넣어도 루트 노드에 닿게 될 거다.

int findRoot(int n) {
	int pnode = toParent[n];
	if (pnode == 0) {
		return n;
	}
	else {
		return findRoot(pnode);
	}
}

재귀를 통해 루트 노드를 찾는 함수를 만들었다.

 

나머지는 트리 전처리, LCA를 짜주면 끝난다.

[AC 코드]

#include <iostream>
#include <vector>
#include <queue>
#define MAX (100000 + 1)

using namespace std;
vector<int> adj[MAX];
int toParent[MAX];
int level[MAX];
int parent[MAX];

int findRoot(int n) {
	int pnode = toParent[n];
	if (pnode == 0) {
		return n;
	}
	else {
		return findRoot(pnode);
	}
}

void swap(int* a, int* b) {
	int* temp = a;
	a = b;
	b = temp;
	return;
}

void treeSet(int node, int pnode) {
	level[node] = level[pnode] + 1;
	parent[node] = pnode;

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

		treeSet(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;
}

int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	int T;
	cin >> T;
	for (int t = 0; t < T; t++) {
		int n;
		cin >> n;
		for (int i = 1, a, b; i < n; i++) {
			cin >> a >> b;
			adj[a].push_back(b);
			toParent[b] = a;
		}

		int rootNode = findRoot(n);
		treeSet(rootNode, 0);
		int s, e;
		cin >> s >> e;
		cout << lca(s, e) << '\n';

		for (int i = 1; i <= n; i++) {
			adj[i].clear();
			toParent[i] = 0;
		}
	}
	return 0;
}