[알고리즘] 백준 11437번: LCA (C++), 최소 공통 조상

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

11437번: LCA

이번에 공부했던 알고리즘은 LCA (Lowest Common Ancestor, 최소 공통 조상)이다.

우선 공부했던 블로그들

(https://zoomkoding.github.io/algorithm/2019/07/27/LCA.html)

(https://4legs-study.tistory.com/121)

[개요]

• 트리에서 두 정점이 주어졌을 때, 두 정점의 조상(부모) 노드 중 공통되며 가장 가까운 노드가 무엇인지를 알아내는 알고리즘

[구현]

이 알고리즘은 개요와 구현 또한 간단한 알고리즘이다.

다만, 조금 생각해야 할 포인트가 있다.

두 정점이 각각 한 번씩 부모 노드로 올라가고, 그 순간마다 둘이 같은 노드인가를 판단해야 하는데 depth(level)가 다르다면 복잡해진다.

그래서 두 노드의 깊이가 같게끔 만들어줘야 한다.

하지만, 그보다 전에 트리를 만들어줘야 노드의 깊이를 같게 하거나 같은 노드인지를 판단하거나 할 수 있기 때문에 트리부터 만들어주자.

 

[트리 구성: treeSet]

한 노드마다 다음 정보를 가지고 있어야 한다.

• level(depth)는 얼마인가?
• parent node는 무엇인가?
• child node는 무엇인가?

그리고, 그 외의 정보로 트리 자체가 가지고 있어야 하는 정보는

• root node는 무엇인가?

이번 문제에서 root node는 1로 주어졌기 때문에 이번 포스팅에서는 신경 쓰지 않도록 하자.

다음 정보들을 담아주기 위해 다음 배열들을 선언해주자.

vector<int> adj[MAX]; // adj[i][index] = j, i와 j가 연결되어있다.
int level[MAX]; // level[i] = value, 노드i의 level은 value다.
int parent[MAX]; // parent[i] = j, i의 부모 노드는 j이다.

주석으로 해당 배열이 어떤 역할을 하는지 주석으로 달아두었다.

그럼 이제 트리를 구성하는 함수를 만들어주도록 하자. 총 2가지 방법이 있다.

• DFS (Recursive Call)
• DFS (Recursive Call, Visited Check)
• BFS (Visited Check)

사실 3가지 중 무얼 써도 똑같고, 심지어 DFS 두 개는 거의 똑같다.

DFS (Recursive Call)만 주석으로 설명해두고, 나머지는 코드만 올려두겠다.

(여담이지만 3가지 코드 중 BFS가 가장 효율적인 거 같긴 하다. 메모리가 2000KB 차이가 나고, 시간은 4ms 정도 빠르다.)

[DFS (Recursive Call)]

// 여기서 pnode는 parent node를 의미함
void treeSet(int node, int pnode) {
	// 루트 노드부터 시작
	level[node] = level[pnode] + 1; // 깊이 갱신
	parent[node] = pnode; // 부모 노드 갱신

	for (int i = 0; i < adj[node].size(); i++) {
		int child = adj[node][i];
		if (child == pnode) continue; //부모 노드로 돌아가면 안 된다.
        // 양방향으로 저장해둬서 pnode로도 갈 수 있는 방법이 있기 때문에 continue 시킨다.

		treeSet(child, node); // recursive call
	}
}

[DFS (Recursive Call, Visited Check)]

void treeSet(int node, int pnode) {
	// 루트 노드부터 시작
	level[node] = level[pnode] + 1;
	parent[node] = pnode;
	visited[pnode] = 1;

	for (int i = 0; i < adj[node].size(); i++) {
		int child = adj[node][i];
		if (visited[child]) continue;
        // child가 pnode가 되어버리는 경우 continue

		treeSet(child, node);
	}
}

[BFS (Visited Check)]

void treeSet(int root) {
	queue<int> q;
	q.push(root);
	level[root] = 1;
	visited[root] = 1;
	while (!q.empty()) {
		int pnode = q.front();
		q.pop();
		for (int i = 0; i < adj[pnode].size(); i++) {
			int cnode = adj[pnode][i];
			if (visited[cnode]) continue;
			visited[cnode] = 1;
			level[cnode] = level[pnode] + 1;
			parent[cnode] = pnode;
			q.push(cnode);
		}
	}
}

 

[LCA]

트리 구성만 살짝 생각했어야 하고, LCA 알고리즘 간단하다.

주석만으로도 설명이 될 정도로 간단하다.

int lca(int a, int b) {
	// 1) 깊이가 더 깊은 걸 a로 swap
	if (level[a] < level[b]) swap(a, b);

	// 2) 깊이 같게 만들기
	while (level[a] != level[b]) {
		a = parent[a];
	}

	// 3) 부모 노드가 같아질 때까지 부모 노드 갱신 반복
	while (a != b) {
		a = parent[a];
		b = parent[b];
	}

	return a;
}

[시간 복잡도]

트리 전처리: O(n)

LCA: 최악의 경우 한쪽으로 치우쳐진 트리일 때, O(n)

>> 이런 시간 복잡도가 나오는 이유가 감이 잡히긴 하나 나중에 제대로 정리해두고 싶다.

[AC 코드]

#include <iostream>
#include <vector>
#include <queue>
#define MAX (50000 + 1)
using namespace std;

vector<int> adj[MAX];
int level[MAX];
int parent[MAX];
bool visited[MAX];
int n;

void swap(int* a, int* b) {
	int* temp = a;
	a = b;
	b = temp;
	return;
}

// 여기서 pnode는 parent node를 의미함
void treeSet(int root) {
	queue<int> q;
	q.push(root);
	level[root] = 1;
	visited[root] = 1;
	while (!q.empty()) {
		int pnode = q.front();
		q.pop();
		for (int i = 0; i < adj[pnode].size(); i++) {
			int cnode = adj[pnode][i];
			if (visited[cnode]) continue;
			visited[cnode] = 1;
			level[cnode] = level[pnode] + 1;
			parent[cnode] = pnode;
			q.push(cnode);
		}
	}
}

int lca(int a, int b) {
	// 1) 깊이가 더 깊은 걸 a로 swap
	if (level[a] < level[b]) swap(a, b);

	// 2) 깊이 같게 만들기
	while (level[a] != level[b]) {
		a = parent[a];
	}

	// 3) 부모 노드가 같아질 때까지 부모 노드 갱신 반복
	while (a != b) {
		a = parent[a];
		b = parent[b];
	}

	return a;
}

int main() {
	cin >> n;
	for (int i = 1, a, b; i < n; i++) {
		cin >> a >> b;
		adj[a].push_back(b);
		adj[b].push_back(a);
	}

	treeSet(1);
	int m;
	cin >> m;
	for (int i = 0, a, b; i < m; i++) {
		cin >> a >> b;
		cout << lca(a, b) << '\n';
	}
	return 0;
}