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

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

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

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 #include 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

", node_b + 1); delete[] visited; delete[] tree; } return 0; }

그 외

from http://popoli31.tistory.com/198 by ccl(A) rewrite - 2021-12-13 19:26:39