[백준] LCA 11437번 C++ 풀이

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

11437번: LCA

 

전체 코드

#include <iostream>
#include <vector>
using namespace std;
vector<int> v[50001];
int parent[50001];
int depth[50001];
int N,M;

void DFS(int x)
{
	for (int i = 0; i < v[x].size(); i++)
	{
		if (depth[v[x][i]] == -1)
		{
			depth[v[x][i]] = depth[x] + 1;
			parent[v[x][i]] = x;
			DFS(v[x][i]);
		}

		// 틀린코드 (1)
		/*
		depth[v[x][i]] = depth[x] + 1;
		if (depth[v[x][i]] == -1)
		{
			parent[v[x][i]] = x;
			DFS(v[x][i]);
		}
		*/
	}
}
int LCA(int a, int b)
{
	if (depth[a] < depth[b])
	{
		int temp = a;
		a = b;
		b = temp;
	}

	while (depth[a] != depth[b])
	{
		a = parent[a];
	}

	while (a != b)
	{
		a = parent[a];
		b = parent[b];
	}

	// 틀린코드(2)
	/*while (parent[a] != parent[b])
	{
		a = parent[a];
		b = parent[b];
	}
	return parent[a];
	*/
	return a;
}
int main(void)
{
	int a, b;
	cin >> N;
	for (int i = 0; i < N - 1; i++)
	{
		cin >> a >> b;
		v[a].push_back(b);
		v[b].push_back(a);
	}

	fill(depth, depth+ N + 1, -1);
	depth[1] = 0;
	DFS(1);

	cin >> M;
	for (int i = 0; i < M; i++)
	{
		cin >> a >> b;
		cout<<LCA(a, b)<<"\n";
	}
}

 

풀이 알고리즘

1. 입력을 받은 노드의 깊이가 같게 움직입니다.

2. 같은 노드를 가리킬 때까지 parent를 타고 올라갑니다.

3. 같은 노드를 가리킨다면 그 노드가 LCA입니다.

 

위의 알고리즘은 가장 빠른 시간내에 풀어내는 LCA 알고리즘을 기반으로 짠 코드라 아래의 알고리즘 개념이 필요

https://non-stop.tistory.com/132?category=983343

 

틀린 코드(1)

노드1부터 높이를 갱신해주는데

노드2로 가 노드2의 높이를 1로 갱신해주고

노드2와 연결된 노드1의 높이가 또 노드2의 높이+1을 해버려서

엉뚱하게 노드1의 높이는 2가 되어버립니다.

 

틀린코드(2)

위와 같은 경우 2와 6의 LCA는 2인데 1을 출력합니다.

왜냐하면 높이를 맞추기 위해 둘 다 노드 2를 가리키고 반환을 노드 2의 부모를 해버리기 때문에 1이 출력됩니다.