[백준 11437] LCA

문제 링크 => 11437번: LCA (acmicpc.net)

11437번: LCA

---

트리에서 최소 공통 조상을 구하는 문제이다.

 

아이디어는 1을 최상단 노드로 잡아서 각 노드들의 부모 노드, 깊이등을 설정한 후, 임의의 두 노드의 가장 가까운 공통 조상을 찾도록 하는 것이다.

 

부모 노드를 표현하기 위한 배열 parent[x] 와 깊이 배열 depth[x] 을 먼저 살펴보면 다음과 같다.

parent[x] : x의 부모 노드

depth[x] : x의 깊이 (0, 1, 2, 3, ...)

 

그렇다면 임의의 두노드(x, y)의 가장 가까운 고통 조상을 찾도록 하는 방법은 다음과 같다.

1. 먼저 depth[x] < depth[y] 가 되도록 하는 노드 x, y를 잡도록 한다. (depth[x]가 더 큰 경우 swap(x, y) 한다)
2. depth[x] == depth[y] 가 될때까지 y노드의 depth를 조정해준다. (y의 부모노드로 이동시켜 depth를 조정함)
3. x == y 가 될때까지 x, y를 각각 부모 노드로 계속 이동시킨다. 

풀이 code

#define _CRT_SECURE_NO_WARNINGS
#include <string>
#include <stdio.h>
#include <math.h>
#include <iostream>
#include <vector>
#include <algorithm>
#include <map>
#include <queue>
#include <set>
#include <stack>
#include <time.h>
#define INF 100000000
#define endl '\n'
#define MOD 1000000009
#define ll long long

using namespace std;

vector<int> v[50001];
bool visited[50001];
int parent[50001]; // parent[child] = mom 으로 구성
int depth[50001]; // 1의 depth를 0으로 잡음

void compose_Parent(int start) {
	queue<int> q;
	q.push(start);
	visited[start] = true;

	while (!q.empty()) {
		int mom = q.front();
		q.pop();
		for (int i = 0; i < v[mom].size(); i++) {
			int child = v[mom][i];
			if (!visited[child]) {
				visited[child] = true;
				parent[child] = mom;
				depth[child] = depth[mom] + 1;
				q.push(child);
			}
		}
	}
}

int LCA(int x, int y) {
	// y node의 depth가 더 높도록 
	if (depth[x] > depth[y]) {
		swap(x, y);
	}
	// depth를 동일하게
	while (depth[x] != depth[y]) {
		y = parent[y];
	}
	// node를 동일하게
	while (x != y) {
		x = parent[x];
		y = parent[y];
	}
	return x;
}


int main() {
	ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);

	int n;
	cin >> n;
	for (int i = 0; i < n - 1; i++) {
		int a, b;
		cin >> a >> b;
		v[a].push_back(b);
		v[b].push_back(a);
	}

	compose_Parent(1);

	int m;
	cin >> m;
	for (int i = 0; i < m; i++) {
		int x, y;
		cin >> x >> y;
		cout << LCA(x, y) << endl;
	}

	return 0;
}