백준 / 11437 LCA C++

www.acmicpc.net/problem/11437

11437번: LCA

최소공통조상 트리 문제이다. 트리가 연결되어있을 때 두 노드의 최소 공통 조상을 구하는 문제이다.

 

예를 들어 3-4-5, 3-6-7 으로 트리가 연결되어있으면 5와 7의 최소공통조상은 3인 것이다.

 

틀렸던 풀이

 

1. 처음에는 두 노드 중 더 위에 (깊이가 안 깊은) 있는 노드 A에 대해서 dfs를 이용해 트리를 탐색해 찾고자하는  더 깊은 노드 B가 있는지 판단하고, 없으면 A의 조상 노드에 대해서 다시 탐색하고 하는 방법을 이용했다. 

이를 이용하니 예제 돌릴 때부터 3초 넘게 걸린것 같아 시간초과 뜰 걸 예상하고 제출했는데 시간초과였다.

 

2. 두 번 째는 B의 부모 중 A의 depth와 일치하는 노드를 찾는다. 그 뒤 depth를 하나씩 위로 올리면서 같은 노드를 가리킬 때까지 반복한다. 찾아보니 이것이 LCA였다. 

하지만 왜인지 시간초과가 났다. 다른 사람의 풀이와 비교했을 때 다른 분들은 2의 거듭제곱 순으로 A와 depth가 일치하는 노드를 찾는 것이고 나는 하나씩 찾은 차이였다. 생각해봤을 때 주어진 조건들하에서는 내 방식도 통과할 거라 생각했다. 하지만 시간초과가 났다.

 

성공한 풀이

 

처음에 depth를 계산할 때는 dfs를 이용해 계산했었다. 여기서는 check한 노드를 또 다시 체크하게 만들었다. 그래서 bfs를 이용해 노드를 check하고 depth를 구했다. 그러니 통과했다.

 

코드

#include<iostream>
#include<vector>
#include<queue>
#include<algorithm>
#include<cstring>

using namespace std;

int n, m;
int parent[50001]; // 부모 노드
vector<int>child[50001];
int depth[50001];
bool check[50001];
int result = 1;

void make_map()
{
	cin >> n;
	memset(parent, 0, sizeof(parent));
	memset(check, false, sizeof(check));

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

void cal_depth()
{
	queue<int>q;
	check[1] = true;
	q.push(1);

	while (!q.empty())
	{
		int p = q.front();
		q.pop();

		for (int i = 0; i < child[p].size(); i++)
		{
			int next = child[p][i];
			if (!check[next])
			{
				check[next] = true;
				depth[next] = depth[p] + 1;
				parent[next] = p;
				q.push(next);
			}
		}
	}
}

void find(int node1, int node2)
{
	if (depth[node1] > depth[node2]) // node2를 더 깊은 것으로
		swap(node1, node2);

	while (depth[node1] != depth[node2])
		node2 = parent[node2];

	while (node1 != node2)
	{
		node1 = parent[node1];
		node2 = parent[node2];
	}
	result = node1;
}

int main()
{
	make_map();
	cal_depth();

	cin >> m;
	while (m--) {
		int a, b;
		cin >> a >> b;

		result = 1;
		find(a, b);
		cout << result << '\n';
	}
}