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

문제 설명

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

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

[문제]

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

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

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

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

 

[입력]

 첫 줄에 테스트 케이스의 개수 T가 주어집니다.

 각 테스트 케이스마다, 첫째 줄에 트리를 구성하는 노드의 수 N이 주어집니다. (2 ≤ N ≤ 10,000)

 그리고 그 다음 N-1개의 줄에 트리를 구성하는 간선 정보가 주어집니다. 한 간선 당 한 줄에 두 개의 숫자 A B 가 순서대로 주어지는데, 이는 A가 B의 부모라는 뜻입니다. (당연히 정점이 N개인 트리는 항상 N-1개의 간선으로 이루어집니다!) A와 B는 1 이상 N 이하의 정수로 이름 붙여집니다.

 테스트 케이스의 마지막 줄에 가장 가까운 공통 조상을 구할 두 노드가 주어집니다.

 

[출력]

 각 테스트 케이스 별로, 첫 줄에 입력에서 주어진 두 노드의 가장 가까운 공통 조상을 출력합니다.

 

[예제 입력 1]

2
16
1 14
8 5
10 16
5 9
4 6
8 4
4 10
1 13
6 15
10 11
6 7
10 2
16 3
8 1
16 12
16 7
5
2 3
3 4
3 1
1 5
3 5

[예제 출력 1]

4
3

---

풀이

 공통 조상을 찾으려면 우선적으로 트리를 거슬러 올라갈 수 있어야 한다. 그러기 위해선 현재 트리 구조를 뒤집어서 저장해야 할 필요성이 있다. 애초에 문제 요구 상에서는 현 트리 구조를 그대로 저장할 필요가 없기 때문에, 처음부터 주어지는 트리의 노드들의 부모와 자식을 뒤집어서 저장해 주면 된다.

 이후 주어지는 2개의 노드를 가지고 공통 조상을 찾을 때, 굳이 양쪽을 번갈아가며 무엇을 할 필요가 없다. 우선적으로 한쪽의 조상들을 모두 찾아 저장을 시켜 놓은 다음, 다른 한쪽의 조상을 순차대로 거슬러 올라가며 저장된 자료 구조에서 가장 먼저 찾으면 된다. 그 때 만약 찾는 것에 대해 긍정의 결과가 반환되면, 이를 return 하면 된다.

#include <iostream>
#include <vector>
#include <unordered_set>
#include <cstring>

using namespace std;

int reverseNodeInfor[10001];//뒤집어진 트리 정보를 담을 배열

int findCommonAncestor(int node1, int node2, int N) {//공통 조상 찾기 함수
	unordered_set<int> node1Ancestor;//node1의 조상들이 저장될 자료 구조

	int node1Parent = node1, node2Parent = node2;

	while (reverseNodeInfor[node1Parent] != -1) {//node1들의 조상 저장(자기 자신 포함)
		node1Ancestor.insert(node1Parent);
		node1Parent = reverseNodeInfor[node1Parent];
	}
	//node2의 조상을 거슬러 올라가며 공통조상 찾기
	while (reverseNodeInfor[node2Parent] != -1) {
		if (node1Ancestor.find(node2Parent) != node1Ancestor.end())
			break;
		else
			node2Parent = reverseNodeInfor[node2Parent];
	}

	return node2Parent;
}

int main() {
	int T, N;
	int parent, child, node1, node2;
	vector<int> answer;

	cin >> T;

	for (int i = 0; i < T; i++) {//하나의 케이스 입력 받아 계산
		cin >> N;

		memset(reverseNodeInfor, -1, sizeof(reverseNodeInfor));

		for (int i = 1; i < N; i++) {
			cin >> parent >> child;
			reverseNodeInfor[child] = parent;
		}

		cin >> node1 >> node2;

		answer.push_back(findCommonAncestor(node1, node2, N));
	}

	for (int i = 0; i < T; i++) //답 출력
		cout << answer[i] << endl;

	return 0;
}

---

결과