취미로 코딩하기

※ 글쓴이는 취미로 코딩을 익혀보는 사람이라 정확하지 않은 내용을 담고 있을 수 있다 ※

이번에 볼 문제는 백준 3584번 문제인 가장 가까운 공통 조상이다.
문제는 아래 링크를 확인하자.

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

LCA를 구하는 기본적인 알고리즘을 익혀보자.

x와 y를 루트방향으로 한 칸씩 움직여가면서 공통조상을 찾으려고 한다. 각 노드와 루트 사이의 거리를 노드의 깊이(depth, 또는 level)라 부르기로 하자.

x와 y의 깊이가 다르다면 둘을 루트방향으로 한 칸씩 움직여도 서로 만날 수 없으므로, 더 깊이 있는 노드를 다른 노드의 깊이가 될 때까지 루트방향으로 한 칸씩 먼저 움직여 주자.

x와 y의 깊이가 같아졌다면 x와 y가 같아질 때까지 두 노드를 동시에 한 칸씩 루트방향으로 움직이자. 주어진 그래프는 트리이므로 두 노드는 언젠가 만남이 보장된다.

이와 같은 과정을 구현하기 위해서는 각 노드의 깊이가 얼마인지, 그리고 각 노드의 부모가 어느 노드인지를 빠르게 접근할 수 있게끔 자료를 미리 저장해두어야 함을 관찰하자. 각 노드의 깊이의 경우 루트를 시점으로 하는 트리의 탐색(DFS, BFS 등)으로, 각 노드의 부모 노드는 스파게티 스택(spaghetti stack)(링크) 방식의 트리 저장 등을 이용하면 빠르게 진행할 수 있다.

또한 "~~를 만족할 때까지 노드를 이동"하는 것과 같은 구현은 while문을 이용해 간단히 구현해줄 수 있다.

글쓴이는 아래의 코드를 작성하는 과정에서 그래프의 루트 위에 가상의 "진짜 루트"(0번 노드)가 있는 것과 같이 생각해 루트 노드의 깊이를 1로 계산하였으나, 그 구현 내용은 위의 설명과 크게 다르지 않다.

아래는 제출한 소스코드이다.

#include <iostream>
#include <vector>
#include <cstring>
#include <utility>
using namespace std;

int T, N;
vector<int> G[10001];
int P[10001]; // 노드의 부모
int D[10001]; // 노드의 깊이
int root;

void dfs(int cur, int par) {
	for (auto& nxt : G[cur]) {
		if (nxt == par) continue;
		D[nxt] = D[cur] + 1;
		dfs(nxt, cur);
	}
}

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

	cin >> T;
	while (T--) {
		memset(P, 0, sizeof(P));
		memset(D, 0, sizeof(D));
		cin >> N;
		for (int i = 1; i <= N; i++) G[i].clear();

		for (int i = 1; i < N; i++) {
			int A, B; cin >> A >> B;
			P[B] = A;
			G[A].emplace_back(B);
			G[B].emplace_back(A);
		}
		for (int i = 1; i <= N; i++) {
			if (!P[i]) root = i;
		}

		D[root] = 1;
		dfs(root, 1);

		int x, y; cin >> x >> y;
		if (D[x] < D[y]) swap(x, y);
		while (D[x] > D[y]) x = P[x];
		while (x != y) x = P[x], y = P[y];

		cout << x << '\n';
	}
}