백준 3584번 가장 가까운 공통 조상 (C++)

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

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

 

 우선 이 문제를 처음 접했을 때, 난 LCA알고리즘의 존재를 모르고 풀었다. 때문에 이 풀이가 100퍼센트 맞는 정답이라고는 말할 수 없다. 하지만 코딩테스트에서 모르는 알고리즘이 나와도 풀이할 수 있어야한다.

LCA에 대해서는 다음 포스팅에 할 예정이다.

 

각 자식들은 단 하나의 부모를 가지고 있다.

 

먼저 A의 조상을 타고 올라간다. 그렇다면 루트노드까지 쭉 타고 올라갈 것이다. 그 후 B부터 루트까지 타고 올라간다. 이 때 A의 조상은 방문표시가 되어있을 것이니 B가 타고 올라가다가 이미 방문한 노드를 발견한다면 그 노드가 공통 조상이다. 

 

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

vector<int> node[10001];
bool visited[10001];
int T, N;
int A, B;

void solution_first(int N) {	
	visited[N] = true;
	if (node[N].size() == 0) return;

	int nextNode = node[N][0];
	
	solution_first(nextNode);
}

int solution_second(int N) {
	if (visited[N] == true) return N;
	
	int nextNode = node[N][0];	

	if (visited[nextNode] == true) return nextNode;
	return solution_second(nextNode);
}

void init() {
	for (int i = 0; i < 10001; i++) {
		visited[i] = false;
		node[i].clear();
	}
}

int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cin >> T;
	for (int i = 0; i < T; i++) {
		init();

		cin >> N;
	
		for (int i = 0; i < N - 1; i++) {
			int s, e;
			cin >> s >> e;
			node[e].push_back(s);
		}
		cin >> A >> B;
		solution_first(A);
		int answer = solution_second(B);

		cout << answer << '\n';
	}
}