BaekJoon 3584번: 가장 가까운 공통 조상(C++)

www.acmicpc.net/problem/3584

3584번: 가장 가까운 공통 조상

해당 문제에 관한 내용은 위의 사이트에 들어가면 자세히 확인할 수 있다.

 

풀이법

1) 가장 가까운 조상을 찾기 위해 LCA 알고리즘을 활용하였다.

www.crocus.co.kr/660

LCA(Lowest Common Ancestor) 알고리즘

(LCA 알고리즘에 대해 잘 모른다면 위의 블로그를 참고하는 것을 추천한다.)

2) 방문을 표시할 배열인 visited와 부모 값을 담기 위한 배열인 parent를 선언하였다.

3) 초기값으로 visited의 경우 false로, parent의 경우 자기 자신으로 초기화 해주었다.

4) 공통의 조상을 구해야 하는 u node와 v node를 입력받은 후, u node부터 root까지 이동하며 방문한 곳에는 visited=true 표시를 해주었다.

5) visited[v]==true 조건을 통해 u가 이미 방문한 노드에 v가 도달한 경우 그 곳이 최소 공통 조상이므로 break 해 주었다.

#include <iostream>
#include <vector>
#define MAX 10001
using namespace std;

int parent[10001];
bool visited[10001];
int t, n, a, b, u, v;
int main()
{
	ios::sync_with_stdio(false);
	cin.tie(0);
	cin >> t;
	for (int  k= 0; k < t; k++)
	{
		cin >> n; //입력 개수
		for (int i = 1; i <= n; i++)
		{
			visited[i] = false;
			parent[i] = i;//자기 자신을 부모로 초기화
		}
		//간선 정보 입력
		for (int i = 0; i < n-1; i++)
		{
			cin >> a >> b;
			parent[b] = a;
		}
		cin >> u >> v;//찾아야 하는 값
		visited[u] = true;
		while (u != parent[u])//내가 루트가 아닌 경우
		{
			u = parent[u];//부모로 올라가고
			visited[u] = true;//방문을 참으로 만든다.
		}
		while (1)
		{
			if (visited[v] == true)
			{
				cout << v << "\n";
				break;
			}
			v = parent[v];
		}
	}
}