LCA [c++]

 최소 공통 조상(Lowest Common Ancestor)는 트리(Tree) 구조에서 특정한 두 노드의 공통된 조상 중에서 가장 가까운 조상을 말한다. LCA 알고리즘은 트리에서 두 노드사이의 거리를 빠르게 구하는ㅇ 등의 다양한 계산에 활용될 수 있다는 특징이 있다. 여기서 다룰 알고리즘은 일종의 dynamic programming이며 최소 공통 조상을 빠르게 찾아내는 알고리즘이다.

 

트리 예

 노드를 거슬러 올라가 보면 15와 20의 LCA는 1이다. 이를 구하는 방법은

 

1. 모든 노드에 대한 깊이(depth)를 구한다.

2. 모든 노드에 대한 2^i번째 부모 노드를 구한다.

3. 최소 공통 조상을 찾을 두 노드를 설정한다.

4. 두 노드의 깊이(depth)가 동일하도록 거슬러 올라간다.

5. 최상단 노드부터 내려오는 방식으로 두 노드의 공통 부모를 찾아낸다.

 

cf) 루트 노드를 0으로 생각하고 구현하면 수월하다.

 

// 1. 모든 노드에 대한 깊이를 구함
// 2. 모든 노드에 대한 2^i번째 부모 노드를 구함
// 3. 최소 공통 조상을 찾을 두 노드를 설정
// 4. 두 노드의 깊이가 동일하도록 거슬러 올라감
// 5. 최상단 노드부터 내려오는 방식으로 두 노드의 공통 부모를 찾아냄

#include <iostream>
#include <vector>
#define MAX 1001
#define LOG 11 // 전체 노드의 갯수는 2^10개 이하

using namespace std;

int n, m, parent[MAX][LOG], d[MAX]; // 정점, 간선, parnet[x][1]은 x의 2^1번째 부모, 깊이
bool c[MAX]; // 방문한 노드인지
vector<int> a[MAX];


// 바로 윗 부모와 연결하는 함수
void dfs(int x, int depth) {
c[x] = true; // 방문표시
d[x] = depth; // 깊이입력
for (int i = 0; i < a[x].size(); i++) {
int y = a[x][i];
if (c[y]) continue; // 이미 방문한 노드면 건너 뜀
parent[y][0] = x; // y의 (1)번째 부모는 x
dfs(y, depth + 1); // y의 깊이는 d[x] + 1
}
}

// 전체 부모 관계를 설정하는 함수
void setParent() {
dfs(0, 0); // 루트를 0으로 설정
for (int j = 1; j < LOG; j++) {
for (int i = 0; i < n; i++) {
parent[i][j] = parent[parent[i][j - 1]][j - 1];
}
}
}

// 최소 공통 조상을 찾는 함수
int LCA(int x, int y) {
// y가 깊이가 더 깊도록 설정
if (d[x] > d[y]) swap(x, y);

// 두 노드의 깊이를 동일하도록 맞춤
for (int i = LOG - 1; i >= 0; i--) {
if (d[y] - d[x] >= (1 << i)) { // y의 x의 깊이의 차이가 2^i 보다 크다면
y = parent[y][i]; // y의 i번째 부모값으로 변경
}
}

// 부모가 같은 경우 반환
if (x == y) return x;

//조상을 향해 위에서 아래로 확인
for (int i = LOG - 1; i >= 0; i--) {
if (parent[x][i] != parent[y][i]) {
x = parent[x][i];
y = parent[y][i];
}
}
return parent[x][0];
}


int main() {
n = 21;

a[0].push_back(1);
a[1].push_back(0);

a[0].push_back(2);
a[2].push_back(0);

a[1].push_back(3);
a[3].push_back(1);

a[1].push_back(4);
a[4].push_back(1);

a[2].push_back(5);
a[5].push_back(2);

a[2].push_back(6);
a[6].push_back(2);

a[3].push_back(7);
a[7].push_back(3);

a[3].push_back(8);
a[8].push_back(3);

a[4].push_back(9);
a[9].push_back(4);

a[4].push_back(10);
a[10].push_back(4);

a[4].push_back(11);
a[11].push_back(4);

a[8].push_back(13);
a[13].push_back(8);

a[9].push_back(14);
a[14].push_back(9);

a[10].push_back(15);
a[15].push_back(10);

a[13].push_back(16);
a[16].push_back(13);

a[13].push_back(17);
a[17].push_back(13);

a[14].push_back(18);
a[18].push_back(14);

a[15].push_back(19);
a[19].push_back(15);

a[17].push_back(20);
a[20].push_back(17);

setParent();


cout << "7와 20의 LCA :" << LCA(7, 20) << endl;
cout << "5와 7의 LCA :" << LCA(5, 7) << endl;
cout << "15와 20의 LCA :" << LCA(15, 20) << endl;
cout << "16와 17의 LCA :" << LCA(16, 17) << endl;
cout << "10와 9의 LCA :" << LCA(10, 9) << endl;
cout << "3와 17의 LCA :" << LCA(3, 17) << endl;

return 0;
}