[C++][백준] LCA 2(11438)

문제

N(2 ≤ N ≤ 100,000)개의 정점으로 이루어진 트리가 주어진다. 트리의 각 정점은 1번부터 N번까지 번호가 매겨져 있으며, 루트는 1번이다.

두 노드의 쌍 M(1 ≤ M ≤ 100,000)개가 주어졌을 때, 두 노드의 가장 가까운 공통 조상이 몇 번인지 출력한다.

 

입력

첫째 줄에 노드의 개수 N이 주어지고, 다음 N-1개 줄에는 트리 상에서 연결된 두 정점이 주어진다. 그 다음 줄에는 가장 가까운 공통 조상을 알고싶은 쌍의 개수 M이 주어지고, 다음 M개 줄에는 정점 쌍이 주어진다.

 

출력

M개의 줄에 차례대로 입력받은 두 정점의 가장 가까운 공통 조상을 출력한다.

 

풀이

문제의 제목 그대로 LCA 알고리즘을 사용하여 풀이하였습니다.

LCA 알고리즘은 아래 블로그를 참고하시면 도움되실 것 같습니다.

www.crocus.co.kr/660

LCA(Lowest Common Ancestor) 알고리즘

LCA 알고리즘은 O(logN) 시간복잡도로 두 노드의 최소 공통 조상을 찾을 수 있는 알고리즘입니다.

간략하게 정리하면 아래와 같습니다.

 

LCA(A, B) 
1. DFS, DP를 통해 A, B 노드의 depth, 조상 노드를 구합니다.
2. A, B 노드의 깊이를 맞춰줍니다.
 - 깊이가 더 깊은 노드의 깊이를 위로 올려줍니다.
 - A, B 노드가 동일한 경우 해당 노드가 최소 공통 조상입니다.
3. A, B 노드의 조상이 다르다면 조상이 같아질때까지 동시에 거슬러 올라갑니다.

 

코드를 통해 알아보도록 하겠습니다.

 

1-1. DFS를 통해 A, B 노드의 depth, 부모 노드를 구합니다.

int depths[MAX];
int parents[MAX][25];

// 전처리를 수행한다.
// 각 노드의 깊이, 부모를 계산한다.
void preprocessing1(int cur, int depth, int parent) {
	visited[cur] = true;
	depths[cur] = depth;
	parents[cur][0] = parent; // parent는 cur노드의 바로 위 부모

	for (int i = 0; i < myGraph[cur].size(); i++) {
		int next = myGraph[cur][i];

		if (visited[next] == false) {
			preprocessing1(next, depth + 1, cur);
		}
	}
}

cur 노드의 깊이는 depth[cur]에 담아주고

cur 노드의 부모는 parents[cur][0]에 담아주었습니다.

 

1-2. DP를 통해 A, B 노드의 조상 노드를 구합니다.

void preprocessing2 () {
	for (int j = 1; j < 20; j++) {
		for (int i = 1; i <= N; i++) {
			parents[i][j] = parents[parents[i][j - 1]][j - 1];
		}
	}
}

 

parent[n][k] : n번 노드의 2^k 번째 위 조상 노드

parent 배열을 위와 같이 정의했을 때

parent[n][0]은 n번 노드의 2^0(1) 번째 위 노드이기 때문에 바로 위 부모 노드를 의미합니다.

parent[n][k]는 parent[n][k] = parent[parent[n][k-1]][k-1]이라는 점화식을 세울 수 있습니다.

 

해당 점화식을 채워 n번 노드의 모든 조상 노드를 구해줍니다.이때 점화식을 세우는 순서로 고려해야 합니다.

 

우리는 1-1 과정을 통해 parent[1][0]을 구했습니다.이 정보와 점화식을 통해 parent[1][1], parent[1][2], parent[1][3]을 구할 수 있는지 확인해봅시다.

 

parent[1][1], parent[1][2], parent[1][3] 와 같이 깊이 파고드는 순서로는 구할 수 없습니다.

그러나 parent[1][1], parent[2][1], parent[3][1] 와 같이 넓게 퍼지는 순서대로라면 구할 수 있습니다.

 

void preprocessing2 () {
	for (int j = 1; j < 20; j++) {
		for (int i = 1; i <= N; i++) {
			parents[i][j] = parents[parents[i][j - 1]][j - 1];
		}
	}
}

 

2. A, B 노드의 깊이를 맞춰줍니다.

 - 깊이가 더 깊은 노드의 깊이를 위로 올려줍니다.

// 1. 두 노드의 깊이가 다르다면 깊이를 맞춰준다.
	if (depths[first] != depths[second]) {
		// 편의를 위해 first 노드의 깊이가 더 깊도록 설정한다. 
		if (depths[first] < depths[second]) {
			int tmp = second;
			second = first;
			first = tmp;
		}

		while (depths[first] != depths[second]) {
			for (int i = 20; i >= 0; i--) {
				if (depths[parents[first][i]] >= depths[second]) {
					first = parents[first][i];
				}
			}
		}
	}

편의를 위해 무조건 first 노드의 깊이가 더 깊도록 만들어줍니다.

 

그리고 깊이가 더 깊은 노드의 깊이를 위로 올려주는데 한 노드 한 노드씩 위로 올려주면 비효율적이기 때문에2^k 단위로 훌쩍 훌쩍 올려줍니다. 이 때 시간 복잡도를 O(N)에서 O(logN)으로 줄여줄 수 있습니다.

 

훌쩍 훌쩍 올려주되 second 노드보다 깊이가 올라가면 안되겠죠? second 노드보다 깊이가 같거나 낮은 조건에서 올려줍니다. 

 

여기서 왜 2^20 번째 위 조상노드까지 구하는지 궁금해지는데요,

정점이 100,000개(최대 갯수)인 트리는 트리의 최대 높이가 100,000입니다. (일자로 늘어진 경우)

따라서 n번 노드의 조상은 100,000번째 위 조상까지만 구해주면 됩니다.

2의 몇승이 100,000이 될지 생각해보면(2^x = 100,000),

2^17이 100,000 보다 크기 때문에 넉넉하게 20으로 잡아주었습니다.

(2^17은 100,000보다 크고 2^20은 1,000,000보다 크다는 사실을 기억해두면 유용합니다. 😆)

 

 - A, B 노드가 동일한 경우 해당 노드가 최소 공통 조상입니다.

// 2. 두 노드가 같다면 해당 노드가 최소 공통 조상 노드이다.
if (first == second) return first;

 

3. A, B 노드의 조상이 다르다면 조상이 같아질때까지 동시에 거슬러 올라갑니다.

마찬가지로 한 노드 한 노드씩 위로 올려주면 비효율적이기 때문에 2^k 단위로 훌쩍 훌쩍 올려줍니다.

	// 3. first 노드와 second 노드의 공통 조상이 다르다면 가능한 만큼 거슬러 올라간다.
	while (parents[first][0] != parents[second][0]) {
		for (int i = 20; i >= 0; i--) {
			if (parents[first][i] != parents[second][i]) {
				first = parents[first][i];
				second = parents[second][i];
			}
		}
	}

depths[0] = -1;

1번 노드부터 시작하기 때문에 0번 노드는 존재하지 않습니다. 따라서 0번 노드의 깊이는 -1로 설정해야 합니다.

그렇지 않은 경우 n번 노드의 2^20번째 위 조상이 없음에도 불구하고 parent[n][20] = 0, depth[depth[n][20]] = 0 이 되버리는 참사가 생길 수 있습니다. 

 

while문을 모두 돌고 나면 first 노드와 second 노드의 조상은 동일할 것입니다. 해당 값을 return 합니다.

return parents[first][0];