[C++] 백준 11437번: LCA

문제 출처

풀이

개인적으로 쉬운 문제라 생각했는데 계속 시간초과가 떠서 당황했다. 도저히 해결할 방법이 없어 여기저기 찾아보니 내가 구현한 것에서 level이라는 개념을 도입해 tree의 level을 같게 만들어준 다음 거기서부터 탐색을 하는 방법이 있었다. 물론 이 방법은 O(n)만큼의 시간이 걸리며 O(logn)만큼의 시간이 걸리는 다른 방법이 있다고 한다. 추후에 설명하도록 하며 코드는 다음과 같다.

#include<iostream>
#include<vector>
#include<algorithm>
#include<queue>
#include<tuple>
#include<map>
#include<stack>
#include<set>

using namespace std;

typedef pair<int, int> ii;

int N, M;
vector<vector<int>> adj;
vector<int> parents;
vector<int> level;

void DFS(int parent, int cur)
{
	level[cur] = level[parent] + 1;
	parents[cur] = parent;
	for ( int child : adj[cur] )
	{
		if ( child == parent )continue;
		DFS(cur, child);
	}
}

void DFS2(int cur, vector<int> &res)
{
	if ( cur == 1 )
	{
		res.push_back(1);
		return;
	}
	res.push_back(cur);
	DFS2(parents[cur], res);
}

int CheckVec(vector<int> &a, vector<int> &b)
{
	int a_idx = a.size() - 1;
	int b_idx = b.size() - 1;
	while ( a_idx >= 0 && b_idx >= 0 )
	{
		if ( a[a_idx] != b[b_idx] ) return a[a_idx + 1];
		a_idx--;
		b_idx--;
	}
	if ( b_idx < 0 ) return b[0];
	else return a[0];
}

int Check(int a, int b)
{
	if ( level[a] < level[b] )
	{
		while ( level[a] != level[b] )
		{
			b = parents[b];
		}

		while ( a != b )
		{
			a = parents[a];
			b = parents[b];
		}
		return a;
	}
	else
	{
		while ( level[a] != level[b] )
		{
			a = parents[a];
		}
		while ( a != b )
		{
			a = parents[a];
			b = parents[b];
		}
		return a;
	}
}
int main()
{
	ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
	cin >> N;
	adj.resize(N + 1, vector<int>());
	parents.resize(N + 1,0);
	level.resize(N + 1, 0);
	for ( int i = 0; i < N - 1; i++ )
	{
		int a, b;
		cin >> a >> b;
		adj[a].push_back(b);
		adj[b].push_back(a);
	}
	DFS(0, 1);
	cin >> M;
	vector<int> real;
	for ( int i = 0; i < M; i++ )
	{
		int a, b;
		cin >> a >> b;
		
		printf("%d\n",Check(a, b));
	}

	


	return 0;
}

처음 DFS를 만들 때 level을 각각의 node에 만들어주었다. 이 level은 Check라는 함수에서 사용되는데 탐색의 시간을 용이하게 하기 위해 level을 맞추는 데에 사용된다. 내가 왜 시간 초과가 발생했냐면 DFS2를 통해 해당 node로 부터 부모 노드까지 가는 경로를 vector에 담은 다음 CheckVec을 통해 비교를 했다. 이렇게 되면 vector에 담는 시간만큼 오버헤드가 발생하기 때문에 시간초과가 났던 것이다. 이걸 방지하고자 level이라는 개념을 넣었고 시간초과가 발생하지 않은 것을 볼 수 있었다.