[알고리즘] LCA(최소 공통 조상) (c++)

LCA(Lowest Common Ancestor)란?

LCA 알고리즘은 임의의 두 정점(u, v)에서 가장 가까운 공통 조상을 찾는 알고리즘이다.

 

 

아래 예시를 보면 쉽게 이해할 수 있을 것이다.

 

트리 예제1

위와 같은 트리가 있을때 14, 16 정점의 LCA는 정점 1이다.

 정점 14의 조상 정점들은 순서대로 9, 5, 2, 1이 있다.

 정점 16의 조상 정점들은 순서대로 12 7, 3, 1이 있다.

정점 14, 16이 함께 공유하는 가장 가까운 조상은 정점 1이 된다.

 

트리 예제2

정점 8, 14의 LCA를 구하면 정점 2가 된다.

 정점 8의 조상 정점들은 순서대로 4, 2, 1이 있다.

 정점 14의 조상 정점들은 순서대로 9, 5, 2, 1이 있다.

정점 8, 14이 함께 공유하는 가장 가까운 조상은 정점 2가 된다.

 

트리 예제3

이번엔 정점 14, 5의 LCA를 구해보자. 두 정점의 LCA는 정점 5가 된다.

기준이 되는 정점도 LCA에 포함될 수 있다.

 

---

LCA 알고리즘

LCA는 다음과 같은 방법으로 간단하게 구할 수 있다.

 1. 두 정점의 높이가 같아질 때 까지 Level이 높은 정점을 부모로 거슬러 올라간다.

 2. 레벨이 같은 두 정점이 가리키는 부모가 같아질 때 까지 두 정점을 함께 부모로 거슬러 올린다.

 3. 처음으로 같은 부모 정점이 나타나면, 해당 정점이 LCA값이 된다.

 

이 방법을 사용하려면, 다음이 필요하다.

 각 정점들의 Level 정보

 각 정점들의 부모 정점 정보

해당 정보가 있다면, x = parent[x], y = parent[y] 연산을 통해 LCA를 구할 수 있다.

이러한 정보들은 정점과 간선 정보를 알고 있다면, dfs 알고리즘을 통해 level과 parent를 초기화 할 수 있다.

 

아래 예시를 통해 LCA 알고리즘의 동작 과정을 이해해보자.

 

트리 예제1

정점 14, 16의 LCA를 구하는 과정이다.

 정점 14, 16의 Level이 서로 같아서 Level을 맞추는 과정은 필요없다.

 부모 정점이 같아질 때 까지 부모 노드로 거슬러 올라간다. x = parent[x], y = parent[y]

 4번의 연산을 반복하면 x == y로 LCA인 정점 1을 구할 수 있다.

 

---

다음은 정점 8, 14의 LCA를 구하는 과정이다.

트리 예제2 - 1

먼저 정점 14의 Level이 더 높기 때문에 정점 8과 같은 Level인 4까지 올려준다.(Level 1이 가장 높다.)

트리 예제 2- 2

그 후 부모로 2번 거슬러 올라가면 LCA인 정점 2가 구해진다.

---

마지막으로 정점 14, 5의 LCA를 구해보자

트리 예제 3

정점들의 Level이 서로 달라 정점 14부터 부모를 거슬러 올라가 Level을 올랐더니 정점 5를 만나 LCA를 바로 구했다.

 

=> Level을 같게 만들어주고 값들이 서로 같으면 LCA로 리턴하는 작업을 추가하자!!

 

LCA 알고리즘 cpp

#include <iostream>
#include <vector>
using namespace std;

int level[100];					// Level 정보 저장
int par[100];					// 부모 정점 정보 저장
vector<int> edges[100];			// 간선 저장

void dfs(int cur, int pre, int Level) {
	level[cur] = Level;			// 레벨 저장
	par[cur] = pre;				// 부모 저장
	for (int i = 0; i < edges[cur].size(); i++) {
		int next = edges[cur][i];
		dfs(next, cur, Level + 1);
	}
}


int LCA(int x, int y) {
	if (level[x] > level[y]) swap(x, y);		// y의 레벨이 x보다 크거나 같게 만들기

	while (level[x] != level[y]) {				// level[x] == level[y] 될 때까지 y 올리기
		y = par[y];
	}

	if (y == x) return x;				// 만약 x와 y가 같다면, x가 LCA

	while (par[x] != par[y]) {			// LCA 발견할 때까지 x, y 올리기
		x = par[x];
		y = par[y];
	}

	return par[x];
}

int main() {
	ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	// 간선 정보
	edges[1].push_back(2);
	edges[1].push_back(3);
	edges[2].push_back(4);
	edges[2].push_back(5);
	edges[3].push_back(6);
	edges[3].push_back(7);
	edges[4].push_back(8);
	edges[5].push_back(9);
	edges[5].push_back(10);
	edges[5].push_back(11);
	edges[7].push_back(12);
	edges[7].push_back(13);
	edges[9].push_back(14);
	edges[9].push_back(15);
	edges[12].push_back(16);

	// 레벨, 부모 초기화
	dfs(1, 0, 1);

	cout << LCA(14, 16) << '\n';
	cout << LCA(8, 14) << '\n';
	cout << LCA(14, 5) << '\n';

	return 0;
}

//출력

1

2

5

 

예제를 통해 확인했던 값과 동일하게 나오는 것을 확인할 수 있다.

 

한계

현재 사용한 방법은 선형적인 방법으로 LCA를 구하는 방법이다.

시간복잡도는 O(최대레벨)이 될 것이다. 그런데 만약

위와 같이 트리의 균형이 맞지 않는 경우 엄청 비효율적일 것이다.

이를 보완하기 위해 더 빠르게 LCA를 구하는 방법이 있다.

---

더 빠르게 LCA 찾기(with DP)

해당 아이디어는 한 정점의 2^k번째 부모들을 저장해두어 더 빠르게 LCA를 찾는 방법이다.

시간복잡도는 O(log(최대 레벨))까지 줄어든다.

 

다이나믹 프로그래밍을 통해 정점의 2^k번째 부모들을 모두 초기화 해주어야 한다.

DP의 점화식은 다음과 같다.

 

Parent[x][k] = Parent[Parent[x][k-1]][k-1]

 

Parent[x][k]는 정점 x의 2^k번째 조상 노드이다.

트리

정점 14의 기준에서 보았을 때

 parent[14][0]은 9가 된다.

 parent[14][1]은 5가 된다.

 parent[14][2]은 1가 된다.

 

DP를 초기화 한 후에 LCA를 구하는 과정은 동일하다.

다만,

 1. level을 동일하게 만드는 과정에선 level[y] - level[x]의 차이가 2^k만큼 차이난다면

y = par[y][k]

                                                                                         를 통해 찾는 과정을 빠르게 만든다.

 2. 공통 조상을 찾는 과정에선 k의 값을 최댓값에서 작아지는 방향으로 적용해서, par[y][k] != par[x][k]인 경우에

y = par[y][k]

x = par[x][k]

                                                                                          를 통해 찾는 과정을 빠르게 만든다.

 

더 빠른 LCA 알고리즘 cpp

#include <iostream>
#include <vector>
using namespace std;

int level[100];					// Level 정보 저장
int par[100][8];					// 부모 정점 정보 저장
vector<int> edges[100];			// 간선 저장

void dfs(int cur, int pre, int Level) {
	level[cur] = Level;			// 레벨 저장
	par[cur][0] = pre;			// 부모 저장
	for (int i = 0; i < edges[cur].size(); i++) {
		int next = edges[cur][i];
		dfs(next, cur, Level + 1);
	}
}


int LCA(int x, int y) {
	if (level[x] > level[y]) swap(x, y);		// y의 레벨이 x보다 크거나 같게 만들기

	for (int k = 7; k >= 0; k--) {
		if (level[y] - level[x] >= (1 << k)) {
			y = par[y][k];
		}
	}

	if (y == x) return x;				// 만약 x와 y가 같다면, x가 LCA

	for (int k = 7; k >= 0; k--) {
		if (par[x][k] != par[y][k]) {
			x = par[x][k];
			y = par[y][k];
		}
	}
	return par[x][0];
}

int main() {
	ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	// 간선 정보
	edges[1].push_back(2);
	edges[1].push_back(3);
	edges[2].push_back(4);
	edges[2].push_back(5);
	edges[3].push_back(6);
	edges[3].push_back(7);
	edges[4].push_back(8);
	edges[5].push_back(9);
	edges[5].push_back(10);
	edges[5].push_back(11);
	edges[7].push_back(12);
	edges[7].push_back(13);
	edges[9].push_back(14);
	edges[9].push_back(15);
	edges[12].push_back(16);

	// 레벨, 부모 초기화
	dfs(1, 0, 1);

	//DP 2^k번째 조상 초기화
	for (int k = 1; k < 8; k++) {
		for (int i = 1; i <= 16; i++) {
			par[i][k] = par[par[i][k - 1]][k - 1];
		}
	}

	cout << LCA(14, 16) << '\n';
	cout << LCA(8, 14) << '\n';
	cout << LCA(14, 5) << '\n';

	return 0;
}

//출력

1

2

5

 

---

관련 문제

LCA

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

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

빠른 LCA

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