[C++]백준 - 3584번 문제

3584번: 가장 가까운 공통 조상 (acmicpc.net)

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

 

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

---

루트가 있는 트리(rooted tree)가 주어지고, 그 트리 상의 두 정점이 주어질 때 그들의 가장 가까운 공통 조상(Nearest Common Anscestor)은 다음과 같이 정의됩니다.

• 두 노드의 가장 가까운 공통 조상은, 두 노드를 모두 자손으로 가지면서 깊이가 가장 깊은(즉 두 노드에 가장 가까운) 노드를 말합니다.

예를 들어  15와 11를 모두 자손으로 갖는 노드는 4와 8이 있지만, 그 중 깊이가 가장 깊은(15와 11에 가장 가까운) 노드는 4 이므로 가장 가까운 공통 조상은 4가 됩니다.

루트가 있는 트리가 주어지고, 두 노드가 주어질 때 그 두 노드의 가장 가까운 공통 조상을 찾는 프로그램을 작성하세요

 

입력

---

첫 줄에 테스트 케이스의 개수 T가 주어집니다.

각 테스트 케이스마다, 첫째 줄에 트리를 구성하는 노드의 수 N이 주어집니다. (2 ≤ N ≤ 10,000)

그리고 그 다음 N-1개의 줄에 트리를 구성하는 간선 정보가 주어집니다. 한 간선 당 한 줄에 두 개의 숫자 A B 가 순서대로 주어지는데, 이는 A가 B의 부모라는 뜻입니다. (당연히 정점이 N개인 트리는 항상 N-1개의 간선으로 이루어집니다!) A와 B는 1 이상 N 이하의 정수로 이름 붙여집니다.

테스트 케이스의 마지막 줄에 가장 가까운 공통 조상을 구할 두 노드가 주어집니다.

 

 

출력

---

각 테스트 케이스 별로, 첫 줄에 입력에서 주어진 두 노드의 가장 가까운 공통 조상을 출력합니다.

 

 

 

---

 

생각해 볼 점

---

정석은 LCA 알고리즘 문제입니다만..

 

더 쉽게 풀어도 됩니다.

 

어차피 단방향 노드이기 때문에, 부모가 확실히 정해져 있고,

 

트리이기 때문에 부모는 노드당 하나 이하로 가질 수 있기 때문입니다.

 

그냥 트리를 만들고, 부모 방향의 간선을 탐색해서 같은 조상이 나오면 출력하면 됩니다.

 

코드

---

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

int main()
{
	int T;
	scanf("%d", &T);
	while (T--)
	{
		int N;
		scanf("%d", &N);
		
		int *tree = new int[N];
		fill_n(tree, N, -1);
		for (int i = 0; i < N - 1; i++)
		{
			int a, b;
			scanf("%d %d", &a, &b);

			a--; b--;
			//역방향(부모를 가리키도록 함)
			tree[b] = a;
		}
		int node_a, node_b;
		scanf("%d %d", &node_a, &node_b);
		node_a--; node_b--;
		bool* visited = new bool[N];
		fill_n(visited, N, false);


		while (0 <= node_a)
		{
			visited[node_a] = true;
			node_a = tree[node_a];
		}
		while (!visited[node_b]) node_b = tree[node_b];

		printf("%d\n", node_b + 1);

		delete[] visited;
		delete[] tree;
	}
	return 0;
}

 

그 외

---