[Baekjoon] 11438번: LCA 2 (Platinum) - C++ 풀이

자료 구조 트리 LCA 희소 배열

문제

문제 링크

N(2 ≤ N ≤ 100,000)개의 정점으로 이루어진 트리가 주어진다. 트리의 각 정점은 1번부터 N번까지 번호가 매겨져 있으며, 루트는 1번이다.

두 노드의 쌍 M(1 ≤ M ≤ 100,000)개가 주어졌을 때, 두 노드의 가장 가까운 공통 조상이 몇 번인지 출력한다.

입력

첫째 줄에 노드의 개수 N이 주어지고, 다음 N-1개 줄에는 트리 상에서 연결된 두 정점이 주어진다. 그 다음 줄에는 가장 가까운 공통 조상을 알고싶은 쌍의 개수 M이 주어지고, 다음 M개 줄에는 정점 쌍이 주어진다.

출력

M개의 줄에 차례대로 입력받은 두 정점의 가장 가까운 공통 조상을 출력한다.

문제 조건

• 목표: N개의 정점으로 이루어진 트리에서 주어진 M개의 노드 쌍에 대한 최소 공통 조상(LCA)을 오프라인으로 효율적으로 구한다.

• 입력 상태: 정점 수 N 및 쿼리 수 M이 최대 100,000개인 대규모 트리 구조 데이터가 주어진다.

• 핵심 조건: 모든 쿼리를 사전에 입력받아 저장하는 오프라인 쿼리 방식을 취하며, DFS 순회 과정에서 Union-Find를 이용해 조상 노드를 관리해야 한다.

---

풀이

핵심 알고리즘

자료 구조

• 시간 복잡도: O((N + M) · α(N)) — N과 M이 100,000일 때 약 10^5~10^6 단위의 연산으로 112ms 내에 처리가 가능하다.

핵심 아이디어

Tarjan’s Offline LCA 알고리즘을 사용한다. DFS로 트리를 탐색하며 자식 노드의 탐색이 종료될 때마다 부모 노드와 합치고(Union), 해당 시점에 방문 가능한 쿼리 쌍이 있다면 Union-Find의 Find 연산을 통해 공통 조상을 즉시 결정한다.

① 오프라인 쿼리 저장 및 양방향 설정

쿼리를 실시간으로 처리하는 대신 모든 쿼리를 노드별 리스트에 저장한다. 특정 노드 u를 방문했을 때 상대 노드 v가 이미 방문된 상태라면 즉시 LCA를 찾을 수 있도록 양방향({u, v}, {v, u})으로 저장하여 DFS 1회 순회 중 반드시 한 번은 조건에 걸리게 한다.

if (!(cin >> M)) return 0;
	for (int i = 0; i < M; i++) {
		int u, v;
		cin >> u >> v;
		queries[u].push_back({ v, i });
		queries[v].push_back({ u, i });
	}

② 경로 압축을 이용한 Find 연산

Union-Find 자료구조의 Find 함수를 구현한다. Path Compression을 통해 트리의 높이를 낮추어, 이후 LCA를 찾기 위해 부모 집합의 대표 원소를 찾는 과정을 상수 시간에 가깝게 최적화한다.

int find(int tar) {
	if (tar == parent[tar]) return tar;
	return parent[tar] = find(parent[tar]);
}

③ DFS 탐색과 서브트리 병합

트리를 후위 순회(Post-order) 방식으로 탐색한다. 자식 노드(next)의 탐색이 완전히 끝난 직후에 parent[next] = curr를 수행함으로써, 해당 자식 서브트리에 속한 모든 노드의 최상위 부모를 현재 노드(curr)로 갱신하여 다음 단계의 LCA 판별을 준비한다.

void LCA(int curr) {
	visited[curr] = true;

	for (int next : adj[curr]) {
		if (!visited[next]) {
			LCA(next);

			// set union
			parent[next] = curr;
		}
	}

④ 방문 상태 확인을 통한 조상 도출

현재 노드(curr)의 모든 자식 탐색이 끝난 시점에서 관련 쿼리들을 검사한다. 쿼리 상대 노드(tar)가 이미 방문(visited[tar] == true) 상태라면, tar가 속한 집합의 대표 원소(find(tar))가 curr와 tar의 가장 가까운 공통 조상이 된다.

	for (auto& query : queries[curr]) {
		int tar = query.first;
		int query_idx = query.second;

		if (visited[tar]) {
			answers[query_idx] = find(tar);
		}
	}
	
}

---

성능

• 메모리 : 18624 KB

• 시간 : 112 ms

코드 (C++)

#define _CRT_SECURE_NO_WARNINGS
#include <iostream>
#include <vector>

using namespace std;

int parent[100'001];
bool visited[100'001];
vector<int> adj[100001];
vector<pair<int, int>> queries[100'001];
int answers[100'001];

// 표준 Path Compression
int find(int tar) {
	if (tar == parent[tar]) return tar;
	return parent[tar] = find(parent[tar]);
}

void LCA(int curr) {
	visited[curr] = true;

	for (int next : adj[curr]) {
		if (!visited[next]) {
			LCA(next);

			// set union
			parent[next] = curr;
		}
	}

	for (auto& query : queries[curr]) {
		int tar = query.first;
		int query_idx = query.second;

		if (visited[tar]) {
			answers[query_idx] = find(tar);
		}
	}
	
}

int main() {
	ios::sync_with_stdio(false);
	cin.tie(NULL);
	//freopen("test.txt", "r", stdin);

	int N, M;
	if (!(cin >> N)) return 0;

	for (int i = 1; i <= N; i++) parent[i] = i;

	for (int i = 0; i < N - 1; i++) {
		int u, v;
		cin >> u >> v;
		adj[u].push_back(v);
		adj[v].push_back(u);
	}

	if (!(cin >> M)) return 0;
	for (int i = 0; i < M; i++) {
		int u, v;
		cin >> u >> v;
		queries[u].push_back({ v, i });
		queries[v].push_back({ u, i });
	}

	LCA(1);

	for (int i = 0; i < M; i++) {
		cout << answers[i] << "\n";
	}

	return 0;
}

---