[백준 C++] 3584 가장 가까운 공통 조상 - 최소공통조상

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

#include <iostream>
#include <list>
#include <queue>
using namespace std;

const int& MaxSize = 10001;

list<int> Children[MaxSize];
pair<int, int> Tree[MaxSize];
queue<int> SearchQueue;

void SearchLCA(int NodeA, int NodeB)
{
	int A = NodeA;
	int B = NodeB;

	while (Tree[A].second != Tree[B].second)
	{
		if (Tree[A].second > Tree[B].second)
		{
			A = Tree[A].first;
		}
		else if (Tree[A].second < Tree[B].second)
		{
			B = Tree[B].first;
		}
	}

	if (A == B)
	{
		cout << A << '\n';
		return;
	}

	while (A != B)
	{
		A = Tree[A].first;
		B = Tree[B].first;
	}

	cout << A << '\n';
}

void InitDepthInfo(int RootNode)
{
	Tree[RootNode].second = 1;

	SearchQueue.emplace(RootNode);
	while (!SearchQueue.empty())
	{
		int Current = SearchQueue.front();
		SearchQueue.pop();

		for (const int& Child : Children[Current])
		{
			Tree[Child].second = Tree[Current].second + 1;
			SearchQueue.emplace(Child);
		}
	}
}

void TestCase()
{
	for (int i = 0; i < MaxSize; ++i)
	{
		Children[i].clear();
		Tree[i] = pair<int, int>();
	}

	int N;
	cin >> N;

	for (int i = 0; i < N - 1; ++i)
	{
		int A, B;
		cin >> A >> B;
		Children[A].emplace_back(B);
		Tree[B].first = A;
	}

	int RootNode = 0;
	for (int i = 1; i <= N; ++i)
	{
		if (Tree[i].first == 0)
		{
			RootNode = i;
		}
	}

	InitDepthInfo(RootNode);

	int NodeA, NodeB;
	cin >> NodeA >> NodeB;

	SearchLCA(NodeA, NodeB);
}

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

	int T;
	cin >> T;
	for (int i = 0; i < T; ++i)
	{
		TestCase();
	}
}

---

 

11437(LCA) 문제와 동일하게 최소 공통 조상 노드를 구하는 문제입니다.

근데 이 문제는 부모 노드를 지정해서 데이터를 입력해주기 때문에 풀이가 더 간단합니다.

BFS 탐색 시 깊이 정보만 저장해주면 나머지 과정은 모두 동일합니다.