[백준 C++] 11437 LCA - 최소공통조상

11437번: LCA

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

const int& MaxSize = 50001;

list<int> Neighbors[MaxSize];
pair<int, int> Tree[MaxSize];
queue<int> SearchQueue;
bool Visited[MaxSize];

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 InitTree(int RootNode)
{
	Tree[RootNode].first = 0;
	Tree[RootNode].second = 1;

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

		if (Visited[Current])
		{
			continue;
		}

		Visited[Current] = true;
		for (const int& Child : Neighbors[Current])
		{
			if (Visited[Child])
			{
				continue;
			}

			Tree[Child].first = Current;
			Tree[Child].second = Tree[Current].second + 1;
			SearchQueue.emplace(Child);
		}
	}
}

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

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

	InitTree(1);

	int M;
	cin >> M;
	for (int i = 0; i < M; ++i)
	{
		int A, B;
		cin >> A >> B;
		SearchLCA(A, B);
	}
}

---

 

트리 그래프에서 두 노드의 최소 공통 조상 노드를 찾는 문제입니다.

풀이 과정은 다음과 같습니다.

 

1. 입력 받은 이웃 노드 정보들을 토대로 루트 노드 부터 BFS 탐색 -> 모든 노드의 부모 노드와 깊이 정보 저장

 

2. 입력 받은 두 노드 간의 최소 공통 조상 탐색

2-1. 두 노드의 깊이 맞추기

2-2. 깊이가 같아졌을 때 두 노드가 같으면 해당 노드 리턴

2-3. 두 노드가 같아질 때까지 각각 부모 노드로 이동 반복

2-4. 두 노드가 같으면 해당 노드 리턴