[백준] 가장 가까운 공통조상

문제 요약

트리가 주어집니다.
2개의 원소를 query로 주면 가장 가까운 공통조상을 구하시오.

아이디어

트리를 구현할 필요가 없다. 그냥 자식에 대해서 부모를 호출할 수 있기만 하면 된다. 이건 1차원 배열(인덱스 : 자식, 값 : 부모) 로 구현할 수 있다.

자기자신을 포함한 ancestor 백터를 각각 구하여
뒤에서부터 비교하며(push_back 땜에 뒤로갈수록 루트에 가깝다.) 처음으로 달라지는 지점을 유의한다.

삽질

입력형식을 잘못이해했다.
각 테케마다 N 개의 줄에 2개씩 정수가 나오는데,
마지막 N번째 줄은 query이지 트리 정보가 아닌데 착각해서 20분 정도를 허비...

소스코드

약 40분 소요

#include<iostream>
#include<vector>
#include<math.h>
using namespace std;
//사진찍고 한 5분 뒤에 시작한 거
int tab[10001];

int get_parent(int child) {
	return tab[child];
}
vector<int> collect_parent(int child) {
	vector<int> ancestors;
	ancestors.push_back(child);//자기자신을 넣고시작
	int parent = tab[child];
	while (parent!=0) {
		ancestors.push_back(parent);
		child = parent;
		parent = tab[child];
	}
	
	return ancestors;
}

void init_tab(int n) {
	for (int i = 0; i <= n; i++) {
		tab[i] = 0;
	}
}

int main() {
	int t;
	cin >> t;
	for (int ctr = 0; ctr < t; ctr++) {
		int n;
		cin >> n;

		init_tab(n);

		int parent, child;
		for (int i = 0; i < n-1; i++) {
			cin >> parent >> child;
			tab[child] = parent;
		}
		int a, b;
		cin >> a >> b;

		vector<int> anc_a = collect_parent(a);
		vector<int> anc_b = collect_parent(b);

		//공통 조상은 뒤에서부터 구한다.
		int ans;
		int min_sz = min(anc_a.size(), anc_b.size());
		for (int i = 0; i < min_sz; i++) {
			int p_a = anc_a.size() - 1 - i;
			int p_b = anc_b.size() - 1 - i;
			if (anc_a[p_a] == anc_b[p_b]) {
				ans = anc_a[p_a];
			}
			else {
				break;
			}
		}
		cout << ans << endl;
	}

}