LCA(Lowest Common Ancestor)란

한국어로는 ‘최소 공통 조상’으로 해석한다. 트리 자료구조에서 특정 노드들의 제일 처음 만나는(깊이가 제일 깊은) parent node를 찾을 때 사용되는 알고리즘이다.

LCA 구현

크게 2 단계로 알고리즘이 작동한다.

  1. DFS, BFS를 이용해 트리의 모든 노드의 depth를 기록한다.
  2. 두 노드의 depth 동일하게 맞추기
  3. 두 노드가 같아질 때까지 트리를 타고 올라가기

코드 1) O(N) LCA

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

  • vector<int> g[50001] : tree 정보를 저장할 adjacent list들
  • vector<int> dep : tree의 각 노드의 depth 정보를 저장
  • vector<int> parent : 각 노드의 parent node 정보를 저장
  • bool v[50001] : dfs에서 노드 방문 처리를 위한 배열

ex. parent[3] = 4라면, 3번 노드의 부모는 4번 노드.

자세한 설명을 주석으로 남겼다.

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;
using ll = long long;

int n, m;
vector<int> g[50001];
vector<int> dep;
vector<int> parent;
bool v[50001];

void dfs(int x, int dept) {
	// cout << x << " - " << dept << endl;
	v[x] = 1;
	dep[x] = dept;
	for(int y: g[x]) {
		if(!v[y]) {
			parent[y] = x;
			dfs(y, dept + 1);
		}
	}
}

int lca(int a, int b) {
	// 1. 두 노드의 depth 맞추기!!!
	while(dep[a] > dep[b]) { // a가 더 깊다면,
		a = parent[a]; // a가 tree를 타고 올라오도록
	}
	while(dep[a] < dep[b]) { // b가 더 깊다면,
		b = parent[b]; // b가 tree를 타고 올라오도록
	}

	// 2. 두 노드 동시에 tree 타고 올라가면서
	//    최소공통조상 찾기!!! (a==b이면 while 탈출)
	while(a != b) {
		a = parent[a]; // a가 tree 타고 올라감
		b = parent[b]; // b가 tree 타고 올라감
	}

	return a;
}

int main() {
    ios::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);

	int a, b;
	cin >> n;
	dep.resize(n+1);
	parent.resize(n+1);
	// 0. Tree 정보를 adjacent list 형태로 저장
	for(int i=0; i<n-1; i++) {
		cin >> a >> b;
		g[a].push_back(b);
		g[b].push_back(a);
	}
	// 0. dfs로 Tree의 모든 노드의 depth 알아내서 저장
	dfs(1, 0); // 1번 노드 : depth = 0

	cin >> m;
	for(int T=0; T<m; T++) {
		cin >> a >> b;
		// LCA 시작!!!!!!!!!!!!!!!!!
		cout << lca(a, b) << "\n"; 
	}
}

코드 2) O(log n) LCA

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

입력 크기가 커졌다. 이 문제를 해결하기 위해서는, 추가적인 메모리를 사용하되 연산 시간을 줄이는 방식을 사용해야 한다. 그러기 위해 parent 배열에 변화를 주었다.

  • vector<int> g[100001] : tree 정보를 저장하는 adjacent list 배열들
  • vector<int> dep : tree의 모든 node의 depth 정보를 저장
  • bool v[100001] : dfs에서 방문처리 배열
  • int parent[100001][22] : 중요!!!!!!!!!!! 각 node의 부모 노드를 저장

parent[n][k] : n번 노드에서 2^k번째 부모 노드 번호

아래 점화식을 이용해 parent 배열을 채운다.

parent[n][k] = parent[parent[n][k-1]][k-1]

#include <iostream>
#include <vector>
#include <algorithm>
#include <cmath>

using namespace std;
using ll = long long;

int n, m;
vector<int> g[100001];
vector<int> dep;
int parent[100001][22];
bool v[100001];
int maxdep = -1;

void dfs(int x, int dept) {
	v[x] = 1;
	dep[x] = dept;
	if(maxdep < dept) maxdep = dept;
	for(int y: g[x]) {
		if(!v[y]) {
			// 첫 번째 부모노드 저장
			parent[y][0] = x; // !! O(n) 버전과의 차이점!
			dfs(y, dept+1);
		}
	}
}

// 점화식을 이용해 parent 배열 채우기
void set_parent() {
	for(int j=1; j<21; j++) {
		for(int i=1; i<=n; i++) {
			// 노드 i의 2^j번째 parent를 구하여 저장
			parent[i][j] = parent[parent[i][j-1]][j-1];
			// 노드 i의 2^j번째 조상은,
			// i의 2^(j-1)번째 조상의 2^(j-1)번째 조상임.
		}
	}
}

int lca(int a, int b) {
	// a랑 b의 depth 같게 맞추기!!
	// 둘 중 depth가 큰 것이 a가 되도록
	if(dep[a] < dep[b]) {
		int tmp = a;
		a = b;
		b = tmp;
	}

	// 1. a의 depth가 b와 같아질 때까지 tree 타고 올라가기
	for(int k=21; k>=0; k--) { // 
		// a와 b의 depth 차이 >= 2^k라면,
		if(dep[a] - dep[b] >= (1 << k)) {
			if(dep[b] <= dep[parent[a][k]]) {
				a = parent[a][k]; // a가 tree 타고 올라가기
			}
		}
	}
	
	
	// 2. a, b 같이 tree 타고 올라가면서 최소공통조상 찾기
	for(int i=21; i>=0 && a != b; i--) {
		if(parent[a][i] != parent[b][i]) {
			a = parent[a][i];
			b = parent[b][i];
		}
	}
	
	int LCA = a;
	if(a != b) {
		LCA = parent[LCA][0]; // 바로 위 조상
	}
	
	return LCA;
}

int main() {
    ios::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);

	int a, b;
	cin >> n;

	dep.resize(n+1);
	dep.assign(n + 1, -1);
	// 0. tree 정보 adjacent list 형태로 저장
	for(int i=0; i<n-1; i++) {
		cin >> a >> b;
		g[a].push_back(b);
		g[b].push_back(a);
	}
	// 0. tree의 모든 노드의 depth 정보 기록
	dfs(1, 0);

	// 
	set_parent(); // 최대 k로 그냥 넣기

	cin >> m;
	for(int T=0; T<m; T++) {
		cin >> a >> b;
		cout << lca(a, b) << "\n";
	}
}

후기

O(n) 버전은 쉬웠다. 알고리즘 개념 이해한 것 그대로 코드로 구현할 수 있었다.

그런데 O(log n)은 애 좀 먹었다. 결국은 책 보고 코드 짰다.

코드에 주석 달면서 복기하니까, 이해가 확실하게 된다.