[백준/C++] 3584. 가장 가까운 공통조상

문제

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

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

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

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

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

 

풀이

입력된 트리의 관계?를 

parent[idx]에 저장했다. 

-> parent[idx] = idx의 부모 번호 

 

노드번호가 1부터 시작함으로, parent[idx] == 0인 노드가 루트 노드임을 알 수 있다. 

 

이렇게 저장한 후에, 입력된 두 노드 A, B에 대해 

자신부터 ~ 루트까지 부모를 계속 거슬러 올라가며 벡터에 저장했다. 

(parent[idx] == 0일 때 까지 거슬러 올라감) 

 

그 다음에, A로 만든 벡터와 B로 만든 벡터의 값을 비교하며, 가장 먼저 같은 노드?번호?가 두 노드의 가장 가까운 공통조상이다. 

 

* 벡터에 부모를 저장할 때, 자기 부모부터 넣는 것이 아니라 자기 자신부터 넣어주어야 한다. 

코드

#include <iostream>
#include <vector>

using namespace std;


int main() {
	int T,N;
	cin >> T;
	for (int t = 0;t < T;t++) {
		cin >> N;
		vector<int> my_parent(10001, 0);
		for (int n = 0;n < N-1;n++) {
			int A, B;
			cin >> A >> B;
			my_parent[B] = A;
		}
		int a, b;
		cin >> a >> b;
		// 루트까지 거슬러 올라가기 
		vector<int> _a; //A ~ 루트까지 거슬러 올라가는 경로 저장 
		vector<int> _b; //B ~ 루트까지 거슬러 올라가는 경로 저장 
		int now = a;
		while (now != 0) {
			_a.push_back(now);
			now = my_parent[now];
		}
		now = b;
		while (now != 0) {
			_b.push_back(now);
			now = my_parent[now];
		}

		// 가장 가까운 공통 조상 찾기 
		bool isFind = false;
		for (int i = 0;i < _a.size();i++) {
			if (isFind) break;
			for (int j = 0;j < _b.size();j++) {
				if (_a[i] == _b[j]) {
					cout << _a[i] << endl;
					isFind = true;
					break;
				}
			}
		}
	}

}

결과