c++/알고리즘

[c++] 백준-LCA2 (Least Common Ancestor)

hojung 2023. 2. 8.

728x90

1. 문제

2. 입출력 및 예제

3. 문제 해설

백준 - lca와 문제는 같다. 그러나 달라진 점이 있다면 노드의 개수가 10000개로 늘었다. 그리고 알아내야하는 노드의 쌍의 수도 늘었다.

이 문제는 그러면 이전 lca문제처럼

bfs나 dfs로 tree의 depth를 알아낸다.
depth가 더 큰 쪽을 parent배열을 이용해 작은쪽과 depth를 맞춘다.
한칸 씩 올리다가 만나는 것이 lca에 해당한다.

위의 알고리즘을 사용하면 시간초과가 나게 된다.

그래서 이 문제는 dp를 적용해 lca + dp를 사용해야한다....

어떤 문제건 두 가지 알고리즘이 섞이면 어렵지만 이 두개는 어려운 것이 두 개가 섞여 더 어려웠다.

한 번에 풀지는 못하고 이 문제의 핵심 아이디어를 찾아 본 후 구현할 수 있었다. 구현 자체는 그렇게 어렵지는 않았다.

나는 이 문제를 크게 5가지 파트로 나누어 생각했다.

입력을 받을 때 트리의 인접리스트를 구성해주어야한다. (방향성이 문제에서 주어지지 않는다. 양쪽 다 저장한다.)
Tree의 depth를 구하는 부분이 존재해야한다.(bfs나 dfs)를 이용해 구할 수 있겠다.
parent배열을 만드는 부분이 필요하다. (dp배열)
위에 만들어진 준비물로 lca를 찾는 과정이 필요하다.
1. 먼저 만약 두 노드의 depth가 다르다면 depth를 맞추는 과정이 필요하다.
2. depth를 맞춘 후 빠르게 공통 조상을 찾아가는 과정이 필요하다.

우선 시간복잡도 상 일반적인 lca알고리즘을 사용하지는 못하고 dp를 통해 memoization해가면서 시간을 줄여야 하는 부분은 알겠다. 그런데 어떤 정보를 저장해야할까? 사실 이 문제를 처음보고 해답을 아는 사람은 그냥 천재인 거 같다.

나는 그 아이디어를 보고 구현만 해보았다.

dp 배열 구성

dp문제를 풀 때는 세 가지 과정을 거쳐야한다.

1. dp배열이 의미하는 것을 정의하는 과정이다.

dp배열 parent[x][k]가 의미하는 것은 x의 2^k번째 부모라는 의미이다.

2. 점화식을 찾아야한다.

parent[x][k] = parent[parent[x][k-1]][k-1]에 해당한다.

3. 초기 값을 정해줘야한다.

parent[x][0] = 자기 바로 위의 부모를 의미한다.

dp배열의 점화식은 다음과 같이 생각해볼 수 있다.

32 = 16+16이다.

16 = 8+8이다.

우리는 dp배열을 x의 2^k 번째 부모로 정의했기 때문에 위의 식이 parent배열에도 적용된다.

즉 32번째 부모는 우리의 16번째 부모의 16번째 부모이고

16번째 부모는 우리의 8번째 부모의 8번째 부모라는 뜻이다.

이 예시를 일반화하면 x의 2^k번째 부모는 x의 2^(k-1)번째 부모의 2^(k-1)번째 부모가 된다.

따라서 parent[x][k]는 x의 2^k번째 부모를 의미하고 parent[x][k-1]은 x의 2^(k-1)번째 부모를 의미하므로

parent[x][k] = parent[parent[x][k-1]][k-1]의 점화식을 만족하게 되는 것이다.

dp 배열 이용

그렇다면 이 만들어진 parent배열을 이용해서 어떻게 빨리 찾아갈까?

답은 이진수의 수학적 원리에 또 숨어있다.

만약 lca를 구하고자 하는 두 노드의 depth차가 13이라고 하자

13은 이진법으로 변환하면 1011(2)에 해당한다.

즉 1이 존재하는 2^자리수를 모두 더하면 13이 되는 것이다.

우리는 이미 2^k번째 부모를 알고있는 dp배열을 만들어주었다.

그러면 위의 13을 어떻게 찾아가야할까?

예전 lca알고리즘이라면 한칸 한칸 올라가 13번만에 찾을 수 있을 것이다.

하지만 2^k번째 부모를 알고 있는 우리라면

1011에서 1번째 자리수가 1이므로 1만큼 이동한다. 2번째 자리수가 1이므로 2만큼 이동한다. 3번째는 0이므로 continue한다. 4번째 자리수가 1이므로 2 ^ (4-1) = 8만큼 이동하면 우리는 13을 4번만에 움직여 찾을 수 있다.

앞서 만든 parent배열은 이와 같은 과정에 이용되는 것이다.

똑같은 depth를 찾은 이후는??

앞에서 설명한 내용을 통해 두 노드의 depth가 다를 때 어떻게 단 시간안에 같은 depth에 해당하는 각 노드의 부모로 이동할 수 있는지에 대해 설명하였다. 그러나 depth가 같다고 두 개의 노드가 같은 공통 조상을 갖는 것은 아니다. 어떻게 또 탐색해야할까?

우리는 parent[x][k] 배열을 이용해 x의 2^k번째 조상을 알 수 있다. 아무리 높이 올라가도 노드의 개수가 100000이라면 2^17번째 부모노드를 넘을 수 없다. 따라서 2^17번째 부모부터 탐색한다.

int l, r; // 최소 공통 조상을 구하려고자 하는 두 노드 현재 depth는 갖게 맞춰져 있다.
//MAXHEIGHT는 100000을 넘는 2의 ^k의 k에 해당한다. == 17 원코드에선 여유롭게 18로 작성
for(int j=MAXHEIGHT; j >= 0; j--) {
    	if(parent[l][j] != parent[r][j]){
        	l = parent[l][j];
            r = parent[r][j];
        }
}

왜 저렇게 될까?

나도 처음에는 2^k번째 부모를 순서대로 k를 감소시켜 가며 탐색하면 간격이 너무 차이나는 거 아닌가 했는데 그림을 그려 생각해보니 다음과 같았다.

만약 8번째 부모와 16번째 부모 사이에 공통조상이 있다고 해보자 그리고 공통 조상은 13번째 부모에 해당했다

그러면 위의 조건식에 따라 두 노드의 16번째 부모를 확인했을 때는 두 부모가 같아 (최소 공통 조상 위의 조상은 같다.)

if조건문을 돌지 않게되고 8번째 부모를 확인했을 때는 두 부모가 달라 if조건문이 성립해 각각 l과 r은 자신의 8번째 부모노드로 둘 다 이동하게 된다.

그리고 검사하는 것은 l과 r의 4번째 부모이다. 맨처음 13번째 노드가 최소공통 조상에 해당했고 현재 8번째 부모로 이동했으니 아직 이동해야하는 부모 칸이 5번이 남았다. 따라서 현재 이 둘의 4번째 부모도 다르므로 l과 r은 처음 두 노드의 depth가 같던 위치에서 8+4 = 12번째 노드로 이동하게 된다.

그리고 검사하는 것은 l과 r의 2번째 부모이다. 12번을 이동했으므로 1번이 남았고 2번째 부모는 이 둘에게 같다. 따라서 이동하지 않는다.

그리고 검사하는 것이 l과 r의 1번째 부모이다. 12번을 이동했으므로 1번이 남았고 둘은 같다. 따라서 이동하지 않는다.

위의 과정을 거치게 되면 과정을 모두 거친 후 1번째 부모가 이 둘의 최소 공통 조상이 된다.

이 또한 이진수의 원리에 의해 1011처럼 이동하게 되는 것이다...

4. 코드 및 결과

#pragma warning (disable : 4996)
/*
	핵심 아이디어
	x의 2^k 번째 조상을 parent[x][k]로 설정한다.
	
	k = 0이라면 바로 위의 부모를 의미하고
	k = 1이라면 2번째 부모를 의미한다.

	parent[x][1] = parent[parent[x][0]][0] -> [x][1]은 2번째 부모를 의미하므로 parent[parent[x][0]][0] 부모의 바로 위 부모를 의미한다.
	parent[x][2] = parent[parent[x][1]][1] -> [x][2]는 x의 4번째 위 부모를 의미하므로 parent[parent[x][1]][1]은 2 * 2 4번째가 된다.
	즉 점화식은 parent[x][k] = parent[parent[x][k-1]][k-1] 이된다. 
*/

#include <cstdio>
#include <vector>
#include <algorithm>
#define HEIGHTMAX 18
#define MAX 100002
using namespace std;
int N; // 노드의 개수
int M; // 최소 공통 조상 알고 싶은 쌍의 개수
int parent[MAX][HEIGHTMAX + 1]; // 부모 저장 dp배열
int depth[MAX]; // depth를 나타내는 배열
vector<int> AL[MAX];
int ans;
void input() {
	scanf("%d", &N);
	for (int i = 1; i < N; i++) {
		int p, c;
		scanf("%d %d", &p,&c);
		AL[p].push_back(c); // 부모와 연결된 자식 노드들 저장
		AL[c].push_back(p); // 방향성이 없다.
	}
}
void makeTreeDfs(int curr) {
	for (auto next : AL[curr]) {
		if (!depth[next]) {
			parent[next][0] = curr; // 바로 위 부모는 현재 노드
			depth[next] = depth[curr] + 1;
			makeTreeDfs(next);
		}
	}
}
void makeParent() {
	for (int j = 0; j < HEIGHTMAX-1; j++) {
		for (int i = 1; i <= N; i++) {
			int p = parent[i][j];
			//점화식 parent[x][k] = parent[parent[x][k-1]][k-1];
			parent[i][j + 1] = parent[p][j];
		}
	}
}
void lca2(int l, int r) {
	if (depth[l] < depth[r]) swap(l, r); // depth가 더 큰 것을 항상 왼쪽에 둔다. 
	int diff = depth[l] - depth[r]; // 두 depth의 차이
	int move = 0;
	int cmp = 1;
	while (diff) {
		if (cmp & diff) {
			l = parent[l][move];
		}
		diff >>= 1;
		move++;
	} // 같은 층으로 만든다. 
	// 같은 층으로 만들었다는 것은 루트까지 같은 depth에 올라갈 수 있다는 뜻
	if (l != r) {
		//가장 높이 존재하는 부모부터 비교한다. 
		//만약 다르다면 그 다른 노드의 부모노드가 최소 공통 조상이다. 
		for (int j = HEIGHTMAX - 1; j >= 0; j--) {
			if (parent[l][j] != parent[r][j]) {
				l = parent[l][j];
				r = parent[r][j]; // 각각 그 다른 노드를 올라간다. 
			}
		}
		ans = parent[l][0]; // 정답은 그 달라진 노드의 바로 위 부모에 해당한다. 
	}
	else {
		ans = l; // 만약 그대로라면 그냥 바로 l
	}
	printf("%d\n", ans);

}
void sol() {
	scanf("%d", &M);
	for (int i = 0; i < M; i++) {
		int l, r;
		scanf("%d %d", &l, &r);
		lca2(l, r);
	}
}
int main() {
	input();
	depth[1] = 1;
	makeTreeDfs(1); // 루트는 1번이다. 
	makeParent(); //parent 배열을 만들어준다. 
	sol();
	return 0;
}