2022-12-13-#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 이하의 정수로 이름 붙여집니다.
테스트 케이스의 마지막 줄에 가장 가까운 공통 조상을 구할 두 노드가 주어집니다.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
2 #테스트 케이스의 개수
16 #트리를 구성하는 노드의 수
1 14 #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 #3과 5의 공통 조상을 구하여라
[출력]
각 테스트 케이스 별로, 첫 줄에 입력에서 주어진 두 노드의 가장 가까운 공통 조상을 출력합니다.
1
2
4
3
[풀이]
- 처음에는 연결 노드를 만들 생각을 했지만 .. 이 문제의 취지와 맞지 않음
- 부모노드 만들기
- 트리 만들기
- 탐색 알고리즘 만들기
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
t = int(input())
for _ in range(t):
n = int(input())
parents = [0] * (n + 1)
for _ in range(n-1):
i, j = map(int, input().split())
#부모노드 만들기
parents[j] = i
a, b = map(int, input().split())
a_list = [0, a]
b_list = [0, b]
#트리 추가
while parents[a]:
a_list.append(parents[a])
a = parents[a]
while parents[b]:
b_list.append(parents[b])
b = parents[b]
#뒤에서부터 탐색
i = 1
while a_list[-i] == b_list[-i]:
i += 1
print(a_list[-i + 1])
[배운점]
- 좀 돌아갔지만, , 트리구조를 직접 구현할 수 있었음