[백준/BOJ] 백준 11437번 : LCA

www.acmicpc.net/problem/11437

11437번: LCA

두 노드가 같은 높이일 때까지 올리고, 같은 높이일 때 같은 노드라면 그것이 공통조상이고, 다른 노드라면 두 노드를 모두 위로 올려 다시 같은 노드인지 확인하는 것을 반복한다.

 

코드

#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;

int n;
int m;
vector<int> adj[50001];
vector<int> height(50001, 0);
vector<int> parent(50001, 0);
vector<int> check(50001, 0);

struct node
{
	int number;
	vector<node*> children;
};

//here가 부모노드인 트리를 만든다.
node* Maketree(int here)
{
	node* tree = new node();

	tree->number = here;
	check[here] = 1; //만든 노드 체크

	for (int i = 0; i < adj[here].size(); i++)
	{
		if (check[adj[here][i]] == 1)
			continue;

		parent[adj[here][i]] = here; //해당 노드의 부모노드는 here
		height[adj[here][i]] = height[here] + 1; 
		tree->children.push_back(Maketree(adj[here][i]));
	}

	return tree;
}

int Solve(int u, int v)
{
	int height_u = height[u];
	int height_v = height[v];

	while (1)
	{
		if (height_u == height_v)
		{
			if (u == v) //공통조상까지 올라 왔을때
				return u;

			else
			{
				u = parent[u]; //u를 올린다
				height_u = height[u];

				v = parent[v]; //v를 올린다
				height_v = height[v];
			}
		}

		else if (height_u > height_v) //같은 높이로 맞춘다
		{
			u = parent[u];
			height_u = height[u];
		}

		else if (height_u < height_v) //같은 높이로 맞춘다
		{
			v = parent[v];
			height_v = height[v];
		}
	}

	return -1;
}

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

	cin >> n;

	for (int i = 0; i < n - 1; i++)
	{
		int a, b;

		cin >> a >> b;

		adj[a].push_back(b);
		adj[b].push_back(a);
	}

	//루트가 1인 트리를 만든다
	node* root = Maketree(1);

	cin >> m;

	for (int i = 0; i < m; i++)
	{
		int a, b;

		cin >> a >> b;

		cout << Solve(a, b) << "\n";
	}

	return 0;
}