문제

11437번: LCA

풀이

두 노드의 공통 조상을 알기 위해서는 노드의 부모를 하나씩 거슬러 올라가며 같은지 확인하는 방법이 있다. 물론 두 노드의 깊이값(루트 노드까지의 거리)이 다를경우 이를 맞춰주어야 한다.
노드 a, b 중에서 a의 깊이가 더 크다면 b의 깊이까지 a의 부모를 거슬러 올라 간 후 깊이가 같아진 시점부터 두 노드 모두 하나씩 부모를 탐색하며 같은지 확인하여 문제를 해결할 수 있다.

하지만 이는 탐색하는데에 $O(n)$의 시간이 걸린다. 탐색하는 부분에서 모든 depth 값을 탐색하지 않고 2의 제곱 수로 띄엄띄엄 탐색하여 탐색 시간을 줄일 수 있다.
이를 통해 $O(log_{2}(n))$까지 탐색시간을 줄일 수 있다.

2차원 parent[n][k] 배열을 선언하여 노드n의 $2^k$ 만큼 거슬러 올라간 부모를 저장한다.
parent 배열을 점화식으로 표현하면
parent[node][level] = parent[ parent[node][level-1] ][level-1]로 표현할 수 있다.

트리에 대한 정보를 이용하여 dfs 탐색을 하여 각 노드의 depth값과 parent 배열을 작성해야 한다.

void dfs(int v){
	for (int next: graph[v]){
		if (depth[next] != -1) continue;
		parent[next][0] = v;
		depth[next] = depth[v] + 1;
		dfs(next);
	}
}

한번의 탐색으로 각 노드의 부모의 부모, 모든 조상을 완성할 수는 없다.
따라서 한번더 세팅하는 작업이 필요하다. 아까의 점화식을 활용하여 parent배열을 완성할 수 있다. 여기서 주의점은 루트노드인 1노드에서는 부모가 정의되어 있지 않기(-1) 때문에 부모가 -1인 노드들은 따로 예외처리하여 segmentation fault를 피해야 한다.

void setParent(){
	for (int level=1; level <= maxDepth; level++){
		for (int node=1; node <= n; node++){
			if (parent[node][level-1] == -1) continue;
			parent[node][level] = parent[parent[node][level-1]][level-1];
			// 점화식, level 모르는 값을 정의하기 위해 아는 값 level-1에서 유도해낸다.
		}
	}
}

모든 세팅이 끝났으니 저장한 정보를 이용하여 실제 LCA를 구하는 작업을 해야 한다.
우선 두 노드가 주어졌을 때 두 노드의 깊이 값을 동일하게 맞추어야 한다.
parent배열을 통해서는 한번에 2의 제곱수만큼 떨어진 부모만 접근이 가능하기 때문에 원하는 위치로 이동하기 위해서는 적당한 위치의 부모에서 갈아타고 그 부모에서 다시 parent배열을 통해 이동하는 방법을 취해야 한다.

int gap = depth[a] - depth[b];
{
    int i = 0;
    while (gap != 0){
        if (gap % 2 == 1){
            a = parent[a][i];
        }
        gap /= 2;
        i++;
    }

}

위의 코드를 잘 살펴보면 마치 2진수를 변환하듯이 작동된다는 것을 알 수 있다. 만약 두 노드간의 깊이 차이가 3이라면 이진수 11(2)로 변환되기 때문에 a에서 $2^0$ 만큼 떨어진 부모로 이동, 이동한 부모에서 다시 $2^1$만큼 떨어진 부모로 이동하여 3만큼 떨어진 부모로 이동할 수 있다.
다른 예로 깊이 차이가 5라면 101(2)이므로 a에서 $2^0$ 만큼 떨어진 부모로 이동, 이동한 부모에서 다시 $2^1$만큼이 아닌 $2^2$만큼 떨어진 부모로 이동하여 총 5만큼 떨어진 부모로 이동할 수 있다.

같은 깊이 값을 가지는 부모로 이동하였다면 두 부모가 값이 같은지 확인하는 작업이 필요하다.
최소 공통 조상임을 확인하기 위해서 가장 루트로 이동 후 각 경로에 맞게 루트에서 자식 하나씩 내려가며 비교한다. 루트는 공통 조상이고 그의 자식으로 한 단계씩 내려가며 같은지 확인하게 되면 언젠가 두 노드로 갈라지는 분기가 생기게 될 것이다. 그렇다면 분기가 생겨 다른 값을 가지는 두 노드의 부모는 첫 공통 부모인 최소 공통 조상 노드가 된다.
최소 공통 조상을 찾기 위해 루트에서부터 탐색하여 처음 다른 노드가 발생하는 지점을 발견한 후 그 노드의 부모를 리턴하는 것이다.

if (a == b) return a;

// 최소 공통 조상 노드 바로 자식까지 이동
for (int i=maxDepth; i >=0; i--){
    if (parent[a][i] == -1) continue;
    if (parent[a][i] != parent[b][i]) {
        a = parent[a][i];
        b = parent[b][i];
    }
}
return parent[a][0]; // 최소 공통 조상 노드의 바로 자식에서 한 단계 부모 = 최소 공통 조상 노드

코드

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

using namespace std;

int maxDepth;
int n, m;
vector<vector<int>> parent;
vector<int> depth;
vector<vector<int>> graph;

void dfs(int v){
	for (int next: graph[v]){
		if (depth[next] != -1) continue;
		parent[next][0] = v;
		depth[next] = depth[v] + 1;
		dfs(next);
	}
}

void setParent(){
	for (int level=1; level <= maxDepth; level++){
		for (int node=1; node <= n; node++){
			if (parent[node][level-1] == -1) continue;
			parent[node][level] = parent[parent[node][level-1]][level-1];
			// 점화식, level 모르는 값을 정의하기 위해 아는 값 level-1에서 유도해낸다.
		}
	}
}

int LCA(int a, int b){
	if (depth[a] < depth[b]) { swap(a,b); } // 깊이가 더 깊은 노드를 a로 설정

	// 두 노드의 깊이를 같도록 이동
	int gap = depth[a] - depth[b];
	{
		int i = 0;
		while (gap != 0){
			if (gap % 2 == 1){
				a = parent[a][i];
			}
			gap /= 2;
			i++;
		}
		
	}

	if (a == b) return a;

	// 최소 공통 조상 노드 바로 자식까지 이동
	for (int i=maxDepth; i >=0; i--){
		if (parent[a][i] == -1) continue;
		if (parent[a][i] != parent[b][i]) {
			a = parent[a][i];
			b = parent[b][i];
		}
	}
	return parent[a][0]; // 최소 공통 조상 노드의 바로 자식에서 한 단계 부모 = 최소 공통 조상 노드
	
}

int main() {
	cin.tie(0);
	ios_base::sync_with_stdio(false);

	cin >> n;
	maxDepth = ceil(log2(n));
	parent.assign(n+1, vector<int>(maxDepth+1, -1));
	depth.assign(n+1, -1);
	graph.assign(n+1, vector<int>());
	for (int i=0; i<n-1; i++){
		int a, b;
		cin >> a >> b;
		graph[a].push_back(b);
		graph[b].push_back(a);
	}
	
	depth[1] = 0;
	dfs(1);
	setParent();

	cin >> m;
	while (m--){
		int a, b;
		cin >> a >> b;
		cout << LCA(a, b) << "\n";
	}

	return 0;
}

참고

https://kibbomi.tistory.com/201