3584_가장 가까운 공통 조상

▶ 골드4 (트리)

 

풀이

부모 노드 값을 가지고 있는 배열: tree

조상을 담을 vector: A

를 선언하고

 

먼저 입력받은 간선 정보를 이용하여 각 노드의 부모 노드를 채워준다.

그 후, 공통 조상을 구할 두 노드 중 첫 번째 노드의 모든 조상 노드들을 A에 삽입한다.

마지막으로 두 번째 노드의 모든 조상 노드를 A에 삽입하는데, 이 때 A에 이미 존재하는 값이라면 이것이 두 노드의 공통 조상 노드이므로 그 값을 출력하고 배열과 vector를 초기화하고 다음 테스트케이스를 진행한다.

 

코드

#include <iostream>
#include <cmath>
#include <vector>
#include <queue>
#include <set>
#include <algorithm>
#include <cstring>
#include <string>
#define MAX 10001
using namespace std;

int tree[MAX];
vector<int> A;
int ans;

void findParent(int tmp) {
	if (find(A.begin(), A.end(), tmp) == A.end()) {
		A.push_back(tmp);
		if (tree[tmp] != 0) {
			findParent(tree[tmp]);
		}
		else {
			return;
		}
	}
	else {
		ans = tmp;
		return;
	}
}


int main() {
	int t;
	cin >> t;
	while (t--) {
		int n;
		cin >> n;
		for (int i = 0; i < n - 1; i++) {
			int a, b;
			cin >> a >> b;
			tree[b] = a;
		}
		int c, d;
		cin >> c >> d;
		findParent(c);
		findParent(d);
		cout << ans << endl;

		// 초기화
		A = vector<int>(MAX, 0);
		memset(tree, 0, sizeof(tree));
		ans = 0;
	}
}