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

11438번: LCA 2

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

const int& MaxSize = 100001;
const int& MaxK = 20;
int K;
int MaxDepth;

list<int> Neighbors[MaxSize];
int Depth[MaxSize];
int Parent[MaxK][MaxSize];
queue<int> SearchQueue;
bool Visited[MaxSize];

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

	if (Depth[A] != Depth[B])
	{
		if (Depth[A] > Depth[B])
		{
			int Temp = A;
			A = B;
			B = Temp;
		}

		int Gap = Depth[B] - Depth[A];
		for (int i = 0; Gap > 0; ++i)
		{
			if (Gap % 2 == 1)
			{
				B = Parent[i][B];
			}

			Gap = Gap >> 1;
		}
	}

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

	int S = K;
	while (S >= 0)
	{
		if (Parent[S][A] != Parent[S][B]
			&& Parent[S][A] != 0
			&& Parent[S][B] != 0)
		{
			A = Parent[S][A];
			B = Parent[S][B];
		}

		--S;
	}

	if (A != B)
	{
		A = Parent[0][A];
		B = Parent[0][B];
	}

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

void DP(int N)
{
	while (true)
	{
		if (pow(2, K) >= MaxDepth)
		{
			--K;
			break;
		}

		++K;
	}

	for (int i = 1; i <= K; ++i)
	{
		for (int j = 1; j <= N; ++j)
		{
			if (Parent[i - 1][Parent[i - 1][j]] == 0)
			{
				continue;
			}

			Parent[i][j] = Parent[i - 1][Parent[i - 1][j]];
		}
	}
}

void InitTree(int RootNode)
{
	Depth[RootNode] = 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;
			}

			Depth[Child] = Depth[Current] + 1;
			MaxDepth = max(MaxDepth, Depth[Child]);
			Parent[0][Child] = Current;
			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);
	DP(N);

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

---

 

일반적인 LCA 문제에서 진화된 형태의 문제입니다.

입력 데이터의 개수가 크게 들어오기 때문에 시간복잡도를 최소화할 수 있도록 DP를 접목해야 풀 수 있습니다.

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

 

1. 일반적인 LCA처럼 BFS를 통해 모든 노드의 부모 노드, 깊이 정보 저장

2. DP 점화식을 이용해서 2의 K승 까지 위에 있는 부모 노드까지 행렬에 저장 (K는 트리 최대 깊이 > 2^K를 만족하는 최대값, 점화식: P[K][N] = P[K - 1][P[K - 1][N]])

3. LCA 탐색

 

LCA 탐색에서 주의할 점입니다.

1. 두 노드의 깊이를 맞춰줄 때 깊이가 깊은 노드를 2의 i승씩 위로 올려줍니다. (i는 1씩 증가, 깊이 차이 값 2씩 나누기)

2. 깊이가 같지만 서로 다른 노드일 때 두 노드의 2^K 번째 부모 중 서로 값이 다른 가장 큰 값으로 이동해가며 K가 0이 될때까지 반복합니다.

 

요약하자면 문제의 핵심은 시간복잡도를 최소화하는 것이며,

이를 위해서 DP를 통해 2^K 부모 노드를 모두 저장하고

LCA 탐색 시 2^K 칸씩 위로 이동하도록 하는 것입니다.