[Gold / 11437] LCA

문제 링크

---

🔷 분류

그래프 이론, 트리, 최소 공통 조상

✒️ 문제 설명

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

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

⬅️ 입력

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

➡️ 출력

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

💻 코드 (C++)

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

vector<vector<int>> tree; // 인접 행렬
int depth[50001];
int parent[50001];
int visit[50001];

void BFS(int node); // 1부터 탐색하며 깊이 & 부모 저장
int lca(int a, int b); // a, b 최소 공통 조상 구하기

int main() {
	ios::sync_with_stdio(0);
	cin.tie(0);
	
	int n;
	cin >> n;
	tree.resize(n + 1);
	for(int i = 0; i < n - 1; i++) { // 간선은 n-1개
		int a, b;
		cin >> a >> b;
		tree[a].push_back(b);
		tree[b].push_back(a);
	}
	
	BFS(1); // 부모, 깊이 저장
	
    int m;
	cin >> m;
	for(int i = 0; i < m; i++) {
		int a, b;
		cin >> a >> b;
		int ans = lca(a, b);
		cout << ans << "\n";
	}	
	return 0;
}

void BFS(int node) {
	queue<int> q;
	q.push(node);
	visit[node] = true;
	int level = 1;
	int now_size = 1; // level 별 size -> * 2 씩 커짐
	int count = 0; // 현재 줄 node 갯수
	
	while(!q.empty()) {
		int now = q.front();
		q.pop();
		for(int next : tree[now]) {
			if(!visit[next]) {
				visit[next] = true;
				q.push(next);
				parent[next] = now; // 부모 저장
				depth[next] = level; // 깊이 저장
			}
		}
		count++;
		if(count == now_size) { // 현재 줄 다 채웠으면
			level++;
			count = 0;
			now_size = q.size();
		}
	}
}

int lca(int a, int b) {
	// a 가 더 깊도록 조정
	if(depth[a] < depth[b]) {
		int temp = a;
		a = b;
		b = temp;
	}
	while(depth[a] != depth[b]) { // a 올려서 깊이 맞추기
		a = parent[a];
	}
	while(a != b){
		a = parent[a];
		b = parent[b];
	}
	return a;
}