boj, 백준) 3584. 가장 가까운 공통 조상 (C/C++)

1. 문제 링크

www.acmicpc.net/problem/3584

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

 

2. 문제 개요

루트가 있는 트리가 주어지고,  트리의 간선들이 주어진다(부모 자식 관계). 그리고 마지막으로 LCA를 찾을 두 노드가 주어진다. 주어지는 두 노드의 LCA를 출력하는 프로그램을 작성하시오.

 

 

3. 문제 힌트

첫 번째로 루트를 찾자.  부모 -> 자식 방향으로 간선이 존재한다고 했을 때, 루트는 어떻게 찾을 수 있을까?

 

두 번째로 LCA알고리즘 대로 진행하면 된다.

 

4. 문제 풀이

LCA알고리즘을 알고 있어야 문제를 풀 수 있다.(아쉽)

 

LCA를 구하기 전에 우선 트리의 root부터 알아야 한다.

 

부모 -> 자식 방향으로 간선을 만들었기 때문에, root는 진입 차수가 0일 것이다. (root로 들어오는 간선이 없다)

이 root를 시작으로 LCA알고리즘을 구현하자.

 

처음으로 depth를 구해야 한다.

depth를 구하기 위해 root를 시작으로 DFS를  구현했고 바로 직전의 부모와 depth를 구했다.

 

그리고 바로 위의 부모 정보를 가지고

2칸 위의 부모, 4칸 위의 부모, 8칸 위의 부모... log2 (n)을 높임한 번째의 부모까지 구했다.

(왜 인지는 다른 훌륭한 분들이 LCA알고리즘 설명해 놓으신 글을 참조 바랍니다 :) )

kibbomi.tistory.com/201

최소 공통 조상 (LCA, Lowest Common Ancestor)(C/C++)

아니면 여기도....

 

2^k승의 부모 정보만 갖고 있는 것은 시간 복잡도를 줄이기 위한 것.

 

깊이, 부모 정보를 모두 구했다면,

LCA를 구해야 하는 두 정점을 선택하고, depth를 같게 만든다. 이때도 지수적으로 움직인다.

 

깊이가 같은 두 정점이 같지 않으면, 부모가 같아질 때까지 움직이고, 그 부모를 출력한다.

두 정점이 같으면 그 정점이 LCA이기 때문에 바로 출력하자.

 

LCA를 구하기 전에 루트를 구하는 게 핵심(?)인 것 같다. 결국 LCA알고리즘을 알아야 풀 수 있는 문제.

 

5. 코드

#include <cstdio>
#include <vector>
#include <algorithm>
#include <cmath>
using namespace std;

void dfs(vector<vector<int>> &adj, vector<int> &depth, vector<vector<int>> &parent, int cur) 
{
	for (int next : adj[cur]) {
		if (depth[next] == -1) {
			depth[next] = depth[cur] + 1;
			parent[next][0] = cur;
			dfs(adj, depth, parent, next);
		}
	}
	return;
}

void connect(vector<vector<int>> &parent, int n, int len)
{
	for (int k = 1; k < len; ++k) 
		for (int i = 1; i <= n; ++i) 
			parent[i][k] = parent[parent[i][k - 1]][k - 1];
	
		return;
}

int LCA(vector<int> &depth, vector<vector<int>> &parent, int u, int v, int len)
{
	//u is deeper than v
	if (depth[u] < depth[v])
		swap(u, v);

	int diff = depth[u] - depth[v];

	for (int k = 0; diff != 0; ++k) {

		if (diff % 2 == 1)
			u = parent[u][k];

		diff /= 2;
	}

	//depth[u] == depth[v]..
	if (u != v) {
		for (int k = len - 1; k >= 0; --k) {
			if (parent[u][k] != parent[v][k]) {
				u = parent[u][k];
				v = parent[v][k];
			}
		}
		u = parent[u][0];
	}
	return u;
}

int main()
{
	int t;
	scanf("%d", &t);

	while (t--)
	{
		int n, root, len;
		scanf("%d", &n);
		vector<vector<int>> adj(n + 1);
		vector<int> depth(n + 1);
		vector<vector<int>> parent(n + 1);
		int u, v;

		len = (int)ceil(log2(n)) + 1;

		for (int i = 0; i <= n; ++i)
			parent[i].resize(len);

		for (int i = 0; i < n - 1; ++i) {
			int p, c;
			scanf("%d %d", &p, &c);
			adj[p].push_back(c);
			++depth[c];
		}

		for (int i = 1; i <= n; ++i)
			if (depth[i] == 0)
				root = i;
		
		fill(depth.begin(), depth.end(), -1);
		depth[root] = 0;

		dfs(adj, depth, parent, root);
		connect(parent, n, len);

		
		scanf("%d %d", &u, &v);
		printf("%d\n", LCA(depth, parent, u, v, len));
	}

	return 0;
}

 

6. 결과