[BOJ] 3584 가장 가까운 공통 조상

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

문제

루트가 있는 트리(rooted tree)가 주어지고, 그 트리 상의 두 정점이 주어질 때 그들의 가장 가까운 공통 조상(Nearest Common Anscestor)은 다음과 같이 정의됩니다.

• 두 노드의 가장 가까운 공통 조상은, 두 노드를 모두 자손으로 가지면서 깊이가 가장 깊은(즉 두 노드에 가장 가까운) 노드를 말합니다.

예를 들어  15와 11를 모두 자손으로 갖는 노드는 4와 8이 있지만, 그 중 깊이가 가장 깊은(15와 11에 가장 가까운) 노드는 4 이므로 가장 가까운 공통 조상은 4가 됩니다.

루트가 있는 트리가 주어지고, 두 노드가 주어질 때 그 두 노드의 가장 가까운 공통 조상을 찾는 프로그램을 작성하세요

입력

첫 줄에 테스트 케이스의 개수 T가 주어집니다.

각 테스트 케이스마다, 첫째 줄에 트리를 구성하는 노드의 수 N이 주어집니다. (2 ≤ N ≤ 10,000)

그리고 그 다음 N-1개의 줄에 트리를 구성하는 간선 정보가 주어집니다. 한 간선 당 한 줄에 두 개의 숫자 A B 가 순서대로 주어지는데, 이는 A가 B의 부모라는 뜻입니다. (당연히 정점이 N개인 트리는 항상 N-1개의 간선으로 이루어집니다!) A와 B는 1 이상 N 이하의 정수로 이름 붙여집니다.

테스트 케이스의 마지막 줄에 가장 가까운 공통 조상을 구할 두 노드가 주어집니다.

출력

각 테스트 케이스 별로, 첫 줄에 입력에서 주어진 두 노드의 가장 가까운 공통 조상을 출력합니다.

---

얼마 전에 익혔던 LCA 알고리즘 문제를 다시 풀어봤다. 공부한지 별로 안 지난 것 같은데 가물가물했다. 이렇게 복습하고 지나가지 않으면 매번 그냥 까먹게 되는 것 같다. 

 

LCA 알고리즘을 요약하면 각 트리 노드들의 깊이를 미리 구해두고 LCA을 구하기 위해 같은 깊이로 맞춰준 다음, LCA를 찾을 때까지 올라간다. 이때 2, 4, 8처럼 2^n번째 부모를 미리 구해두면 더 빠르게 LCA를 구할 수 있다. 어느 정도 수준까지 미리 구해놓느냐는 트리의 최대 크기에 달렸다. ceil(log2n(트리 최대 크기)) 이걸 사용해서 구하면 된다.

 

 

	#include <iostream>
	#include <vector>
	#include <string.h>
	#define MAX 10001
	using namespace std;
	int N, M;
	vector<int> child[MAX];
	bool visited[MAX];
	int depth[MAX];
	int parent[MAX][17];
	void dfs(int x, int d) {
	if (visited[x]) return;
	depth[x] = d;
	visited[x] = true;
	for (int i = 0; i < child[x].size(); i++) {
	int c = child[x][i];
	if (!visited[c]) {
	parent[c][0] = x;
	dfs(c, d + 1);
	}
	}
	}
	void connect() {
	for (int k = 1; k < 16; k++)
	for (int cur = 1; cur <= N; cur++)
	parent[cur][k] = parent[parent[cur][k - 1]][k - 1];
	}
	int LCA(int u, int v) {
	if (depth[u] < depth[v]) {
	swap(u, v);
	}
	int diff = depth[u] - depth[v];
	for (int i = 0; diff != 0; i++) {
	if ((diff & 1) == 1) u = parent[u][i];
	diff = diff >> 1;
	}
	if (u != v) {
	for (int i = 15; i >= 0; i--) {
	if (parent[u][i] != 0 && parent[u][i] != parent[v][i]) {
	u = parent[u][i];
	v = parent[v][i];
	}
	}
	u = parent[u][0];
	}
	return u;
	}
	int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);
	int T;
	cin >> T;
	for (int tc = 0; tc < T; tc++) {
	memset(visited, false, sizeof(visited));
	memset(depth, 0, sizeof(depth));
	memset(parent, 0, sizeof(parent));
	for (int i = 0; i < MAX; i++)
	child[i].clear();
	cin >> N;
	int p, c;
	for (int i = 0; i < N - 1; i++) {
	cin >> p >> c;
	depth[c]++;
	child[p].push_back(c);
	child[c].push_back(p);
	}
	int root;
	for (int i = 1; i <= N; i++) {
	if (depth[i] == 0) {
	root = i;
	break;
	}
	}
	memset(depth, 0, sizeof(depth));
	dfs(root, 0);
	connect();
	cin >> p >> c;
	cout << LCA(p, c) << '\n';
	}
	return 0;
	}

view raw 3584.cpp hosted with ❤ by GitHub

후기)

확실히 백준 문제가 요새 풀고 있는 삼성 역량 테스트 문제에 비해 훨씬 가볍다. 최적화가 거의 필요없기도 하지만 애초에 요구사항이 훨씬 적다. 삼성 문제만 풀다가 백준 문제 푸니까 살 것 같다.