[C/C++] 백준 - 11437번 : LCA

https://www.acmicpc.net/problem/11437

11437번: LCA

문제

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

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

입력

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

출력

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

---

본 문제는 효율성보다는 구현 자체에 초점을 맞춘 문제이다. 최적화를 진행하여 LCA 알고리즘을 시간복잡도 O(logN)으로 구하는 문제는 LCA2 문제이다. 나는 직관적으로 LCA 알고리즘을 이해하기 위해 해당 풀어보았다.

 

본 문제는 Root 노드가 1로 지정되어있다.

내가 생각한 해결 과정은

 

1) Root 노드 1번부터 시작하여 모든 노드를 방문한다. 방문하는 과정에서 Node의 깊이와 Parent 노드를 배열에 저장해준다.

예를 들어, Root 노드의 깊이는 1이고, Root 노드를 부모로 가지는 자식 노드는 깊이가 2이고, Parent 노드는 1이 된다.

void func(int prev, int cur, int dpth){
	parent[cur] = prev;
	visited[cur] = true;
	depth[cur] = dpth;

	for(auto &next : adj[cur]){
		if(!visited[next]){
			func(cur, next, dpth+1);
		}
	}
}

void init(){
	visited[ROOT] = true;
	for(auto &cur : adj[ROOT]){
		func(ROOT, cur, 2);
	}
}

 위와 같이 재귀함수를 통해 모든 노드를 방문하면서 확인해주었다.

 

 그럼 모든 노드에 Depth, Parent Node 정보가 저장되어있을 것이다.

 

2) 이제 확인해야할 것은 최소 공통 조상 노드가 무엇인지 알아내야한다. 나는 깊이가 더 얕은 노드부터 상위 노드로 거슬러 올라가면서 방문 처리를 해주었다. 그리고 Root 노드에 도달했을 경우 종료해주었다. 이렇게 하게 되면 하나의 노드가 가지는 모든 부모 노드들을 방문 처리해두었고, 남은 깊이가 더 깊은 노드도 같은 과정을 진행해준다. 단, 진행하는 과정에서 방문 처리가 되어 있는 노드를 만난다면? 그것이 바로 최소 공통 조상이기에 바로 답을 출력해주고 다음 과정은 진행하지 않는다.

 

※ 사실 깊이가 더 얕은 노드를 시작하든 깊은 노드를 시작하든 하나의 노드는 모든 부모 노드를 방문하며 확인하는 것은 똑같기 때문에 상관 없다.

 

아래는 전체 코드이다.

#include <bits/stdc++.h>
#define fastio ios::sync_with_stdio(false), cin.tie(0), cout.tie(0)
#define INF 1e6 + 3
#define endl '\n'

using namespace std;

typedef long long ll;
typedef unsigned long long ull;

const int MAX_N = 50000;
const int ROOT = 1;

int N, M;
bool visited[MAX_N+1];
int parent[MAX_N+1];
int depth[MAX_N+1];
vector<int> adj[MAX_N + 1];

void func(int prev, int cur, int dpth){
	parent[cur] = prev;
	visited[cur] = true;
	depth[cur] = dpth;

	for(auto &next : adj[cur]){
		if(!visited[next]){
			func(cur, next, dpth+1);
		}
	}
}

void init(){
	visited[ROOT] = true;
	for(auto &cur : adj[ROOT]){
		func(ROOT, cur, 2);
	}
}

void input(){
	cin >> N;
	for(int i=0;i<N-1;i++){
		int x, y;
		cin >> x >> y;
		adj[x].push_back(y);
		adj[y].push_back(x);
	}
}

void getParent(int node){
	visited[node] = true;
	if(node == 1) return;

	getParent(parent[node]);
}

int getCommonParent(int node){
	if(visited[node]) return node;
	return getCommonParent(parent[node]);
}

void solution(){
	cin >> M;

	init();
	while(M--){
		int x, y, answer;
		cin >> x >> y;

		memset(visited, false, sizeof(visited));
		getParent(x);
		answer = getCommonParent(y);

		cout << answer << endl;
	}
}

int main(){
	fastio;
	input();
	solution();

	return 0;
}