11437 LCA (최소 공통 조상) [Gold III]

11437번: LCA

 

문제 풀이 법

1. 연결된 노드 데이터를 BFS를 통해 트리로 만들고 깊이를 저장한다

2. 두 노드의 공통 조상을 찾기 위해 두 노드의 깊이를 맞춘 후 부모 노드로 올라가며 같은 노드가 나오는지 찾는다

#include <iostream>
#include <vector>
#include <cmath>

using namespace std;

vector<vector<int>> tree;
vector<int> depth;
vector<int> parent;
vector<bool> visited;
int executeLCA(int a, int b);
void BFS(int i);

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

	int N;
	cin >> N; 

	tree.resize(N + 1);
	depth.resize(N + 1);
	parent.resize(N + 1);
	visited.resize(N + 1);


	for (int i = 0; i < N - 1; i++)
	{
		int a, b;
		cin >> a >> b;
		tree[a].push_back(b);
		tree[b].push_back(a);
	}
	parent[1] = 0; 
	BFS(1);
	 
	int M;
	cin >> M;

	vector<int> result;
	for (int i = 0; i < M; i++)
	{
		int a, b;
		cin >> a >> b;
		result.push_back(executeLCA(a, b));
	}

	for (int i : result)
		cout << i << "\n";
	 
}

 

int executeLCA(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];
	}
	return a;
}

공통 조상 찾는 코드 부분

 

  
void BFS(int i)
{ 
	// index, level
	queue<pair<int, int>> q;
	q.push(make_pair(i, 0));

	 
	while (q.size())
	{
		int index = q.front().first;
		int level = q.front().second;
		
		visited[index] = true;
		depth[index] = level;
		q.pop();

		 
		for (int i : tree[index]) {
			
			if (visited[i] == true) 
				continue;

			parent[i] = index;
			q.push(make_pair(i, level + 1)); 
		}
	}
}

트리 구성, Depth 찾기