[백준] 골드4 : (3584) 가장 가까운 공통 조상

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

 

자기 자신도 조상에 포함시켜야 한다는 점이 가장 유의해야 할 점이다.

 

현재 조상을 저장할 새 노드를 선언한다.

현재 조상 노드를 a를 시작으로 a의 조상을 거슬려 올라가며 순회한다.

 

현재 조상 노드와 b가 같거나, b의 조상 노드와 같으면 둘의 가장 가까운 공통 조상이다.

현재 b 노드에 대해서 a 노드의 조상을 모두 검사했는데 없으면, 다시 현재 조상 노드를 a로 초기화 후, b를 b의 조상으로 초기화하고 검사를 다시 수행한다.

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

int main()
{
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);

	int T;
	cin >> T;

	while (T--)
	{
		int N;
		cin >> N;

		// 현재 노드의 조상 노드 저장
		vector<int> Nodes(N + 1);

		for (int i = 0, a, b; i < N - 1; ++i)
		{
			cin >> a >> b;
			Nodes[b] = a;
		}

		// temp = 현재 조상
		int a, b, temp;
		cin >> a >> b;
		temp = a; // 현재 노드도 조상 노드로 취급해야 하니, a로 초기화

		while (true)
		{
			// b의 조상이 temp거나, b가 temp인 경우 종료
			if (Nodes[b] == temp || b == temp) { cout << temp << "\n"; break; }
			
			// a의 조상 검사가 모두 끝났으면, b를 b의 조상으로 초기화 후, 현재 조상 초기화
			else if (temp == 0) { b = Nodes[b]; temp = a; }
			
			// a의 조상을 하나씩 증가
			else temp = Nodes[temp];
		}
	}
}