[알고리즘] LCA (Lowest Common Ancestor)

LCA 알고리즘은 트리 혹은 DAG에서 사용하는 알고리즘으로 최소 공통 조상을 구하는 알고리즘이다.

1. 각 트리의 깊이를 구한다. 루트 노드의 깊이는 0이다. 깊이를 구하면서 각 노드의 부모 노드도 저장해둔다.

     - BFS 와 DFS 등으로 구현할 수 있다.

2. 그 다음 각 노드의 2^K 승만큼의 부모 노드를 저장해둔다.

     - 모든 부모 노드를 저장할 필요가 없는 이유는 이진수가 모든 수를 표현할 수 있듯 3번째 조상을 구하려면 1번째           조상의 2번째 조상을 구하면 되기 때문이다.

3. 공통 조상을 구하는 두 노드 u v 중 더 깊은 노드를 같은 높이의 부모노드로 변경한다. 이는 비트 연산자로 구현할 수     있다. 그다음 두 노드들의 가장 윗 노드들부터 내려오면서 확인한다. 이때 두 숫자가 달라지는 시점이 공통 조상의       자식인 시점이며 이 시점의 부모 노드가 최소 공통조상이 된다.

 

아래의 코드는 SWEA 1248번 공통 조상 문제의 코드이다.

#include <iostream>
#include <vector>
#include <cstring>
#include <queue>
using namespace std;
#define MAX 14
int V, E,S,D;
vector <int> adj[10001];
int parent[10001][MAX+1];
int depth[10001];
int lca_node,ans;
void make_depth() {
	queue <int> q;
	int prev = 1;
	for (int next : adj[1]) {
		q.push(next);
		depth[next] = 1;
		parent[next][0] = 1;
	}
	while (!q.empty()) {
		int cur = q.front(); q.pop();
		for (int next : adj[cur]) {
			q.push(next);
			parent[next][0] = cur;
			depth[next] = depth[cur] + 1;
		}
	}
}

void connect() {
	for (int k = 1; k <= MAX; k++) {
		for (int cur = 1; cur <= V; cur++) {
			parent[cur][k] = parent[parent[cur][k - 1]][k - 1];
		}
	}
}

int LCA(int u, int v) {
	if (depth[u] < depth[v]) {
		int temp = u;	u = v;	v = temp;
	}
	int diff = depth[u] - depth[v];
	for(int i = 0; diff != 0; i++) {
		if ((diff & 1))
			u = parent[u][i];
		diff = diff >> 1;
	}
	if (u != v) {
		for (int i = MAX; 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(int argc, char** argv)
{
	int test_case;
	int T;

	freopen("input.txt", "r", stdin);
	cin >> T;

	for (test_case = 1; test_case <= T; ++test_case)
	{
		memset(parent, 0, sizeof(parent));
		memset(depth, -1, sizeof(depth));
		cin >> V >> E >> S >> D;
		for (int i = 1; i <= V; i++)
			adj[i].clear();
		for (int i = 0; i < E; i++) {
			int a, b;
			cin >> a >> b;
			adj[a].push_back(b);
		}
		depth[1] = 0;
		make_depth();
		connect();

		cout << "#" << test_case << " "<< LCA(S, D)<< "\n";
	}
	return 0;//정상종료시 반드시 0을 리턴해야합니다.
}