[백준]11437 LCA 가장 가까운 공통 조상

문제

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

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

입력

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

출력

 

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

 

문제의 예제로 트리를 그려봤습니다.

 

제 풀이는 다음과 같습니다.

 

1. 우선 BFS를 이용해 (정점이 존재하고, 간선의 비용이 모두 동일 + 트리이기때문에 두 정점간 최소이동거리는 정해져있음) 깊이와 정점a에대해 부모노드를 저장.

 

2.깊이가 같을때 까지 재귀를 이용해 탐색

깊이가 같다면, a와 b가 같을 때 까지 부모쪽으로 한칸씩 이동

#include<bits/stdc++.h>

using namespace std;
int n, m;
int d[50001], p[50001];
vector<int>adj[50001];

int lca(int a, int b) {
	if (a == b)return a;
	else if (d[a] > d[b]) {
		//a깊이가 b보다 크면
		return lca(p[a], b);
	}
	else if (d[a] < d[b]) {
		//b깊이가 a보다 크면
		return lca(a, p[b]);
	}
	return lca(p[a], p[b]);
}
int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cin >> n;
	d[1] = 1;
	int a, b;
	for (int i = 0; i < n-1; i++) {
		cin >> a >> b;
		adj[a].push_back(b);
		adj[b].push_back(a);
	}
	cin >> m;
	queue<int>q;
	q.push(1);
	d[1] = 1;
	while (!q.empty()) {
		auto top = q.front(); q.pop();
		for (auto r : adj[top]) {
			if (!d[r]) {
				p[r] = top; //r의 부모는 top
				d[r] = d[top] + 1;
				q.push(r);
			}
		}
	}
	while (m--) {
		cin >> a >> b;
		cout << lca(a, b) << "\n";
	}
}