루트가 있는 트리(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 이하의 정수로 이름 붙여집니다.
테스트 케이스의 마지막 줄에 가장 가까운 공통 조상을 구할 두 노드가 주어집니다.
출력
각 테스트 케이스 별로, 첫 줄에 입력에서 주어진 두 노드의 가장 가까운 공통 조상을 출력합니다.
예제 입력 1
2 16 1 14 8 5 10 16 5 9 4 6 8 4 4 10 1 13 6 15 10 11 6 7 10 2 16 3 8 1 16 12 16 7 5 2 3 3 4 3 1 1 5 3 5 |
예제 출력 1
4 3 |
더보기
Solution
#include<stdio.h>
#include<stdlib.h>
int main(void)
{
int T;
scanf("%d", &T);
for(int t=0;t<T;t++)
{
int N, *parent=NULL, A, B, A_count=0, B_count=0, temp;
scanf("%d", &N);
parent=(int *)calloc(N+1,sizeof(int));
for(int n=1;n<N;n++)
{
scanf("%d%d", &A, &B);
parent[B]=A;
}
scanf("%d%d", &A, &B);
temp=A;
while(parent[temp]!=0)
{
A_count++;
temp=parent[temp];
}
temp=B;
while(parent[temp]!=0)
{
B_count++;
temp=parent[temp];
}
if(A_count>B_count)
for(int a=0;A_count-a>B_count;a++)
A=parent[A];
else if(B_count>A_count)
for(int b=0;B_count-b>A_count;b++)
B=parent[B];
while(A!=B)
{
A=parent[A];
B=parent[B];
}
printf("%d\n", A);
free(parent);
}
return 0;
}
728x90
'백준 알고리즘' 카테고리의 다른 글
<백준 알고리즘> 14370번: 전화번호 수수께끼 (Large) (0) | 2023.02.03 |
---|---|
<백준 알고리즘> 14369번: 전화번호 수수께끼 (Small) (0) | 2023.02.03 |
<백준 알고리즘> 1749번: 점수따먹기 (0) | 2023.02.02 |
<백준 알고리즘> 3020번: 개똥벌레 (0) | 2023.02.02 |
<백준 알고리즘> 2580번: 스도쿠 (0) | 2023.02.02 |