BOJ 3584번 가장 가까운 공통 조상

BOJ : www.acmicpc.net/problem/3584

3584번: 가장 가까운 공통 조상

 

루트가 있는 트리(rooted tree)가 주어지고, 그 트리 상의 두 정점이 주어질 때 그들의 가장 가까운 공통 조상(Nearest Common Anscestor)은 다음과 같이 정의됩니다.

• 두 노드의 가장 가까운 공통 조상은, 두 노드를 모두 자손으로 가지면서 깊이가 가장 깊은(즉 두 노드에 가장 가까운) 노드를 말합니다.

예를 들어  15와 11를 모두 자손으로 갖는 노드는 4와 8이 있지만, 그 중 깊이가 가장 깊은(15와 11에 가장 가까운) 노드는 4 이므로 가장 가까운 공통 조상은 4가 됩니다.

루트가 있는 트리가 주어지고, 두 노드가 주어질 때 그 두 노드의 가장 가까운 공통 조상을 찾는 프로그램을 작성하세요

 

풀이

최근 있었던 코딩테스트에서 LCA를 기반으로 하는 문제가 출제되었는데,

지식이 없어서 풀지 못했었다.

LCA 알고리즘을 공부한 후에 3584번 문제를 풀게 되었는데,

당연히 LCA 로 풀 수 있지만, 어떤 알고리즘이든 기본 베이스가 중요하다고 생각하며, 특히 이 문제는 쿼리의 범위가 작기 때문에 이번에는 LCA 알고리즘이 아닌, 일반 dfs로 문제를 풀어보았다.

 

접근은 LCA 알고리즘과 비슷하게 

1. depth를 갖는 정보를 만들어 준 후에

2. LCA를 알고자하는 두 정점을 입력받으면 두 정점의 depth를 먼저 맞춰주고

3. depth가 동일할 때 두 정점이 다르다면, 다시 parent를 찾아 올라가면서 최소공통조상을 찾아주었다.

 

 

// LCA 알고리즘을 사용하지 않은 풀이

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

int depth[10001];
int parent[10001];
vector<int> v[10001];

void calDepth(int now, int myparent) {

	depth[now] = depth[myparent] + 1;

	for (int i = 0; i < v[now].size(); i++) {
		int next = v[now][i];
		if (next != myparent) {
			calDepth(next, now);
		}
	}

}

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

		for (int i = 1; i < N; i++) {
			int f, s;
			cin >> f >> s;
			v[f].push_back(s);
			parent[s] = f;
		}

		// 루트정점이 뭔지 모르기 때문에, 1~N 중 부모가 없는 정점을 찾는다
		int root;
		for (int i = 1; i <= N; i++) {
			if (parent[i] == 0) {
				root = i;
				break;
			}
		}

		// root 정점부터 depth를 계산한다
		depth[0] = -1;
		calDepth(root, 0);

		// depth 계산이 끝났으면 LCA를 찾는다
		int f, s;
		cin >> f >> s;

		// 정점 f, s의 depth가 다르다면
		if (depth[f] != depth[s]) {
			
			// 정점 f를 상향한다고 가정
			if (depth[f] < depth[s])
				swap(f, s);

			// depth를 맞춘다
			while (depth[f] > depth[s]) {
				f = parent[f];
			}
		}

		// f와 s가 서로 같은 정점이면
		if (f == s) {
			cout << f << "\n";
		}
		else {
			while (parent[f] != parent[s]) {
				f = parent[f];
				s = parent[s];
			}
			cout << parent[f] << "\n";
		}
	}
}