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 이하의 정수로 이름 붙여집니다.
테스트 케이스의 마지막 줄에 가장 가까운 공통 조상을 구할 두 노드가 주어집니다.
출력 :
각 테스트 케이스 별로, 첫 줄에 입력에서 주어진 두 노드의 가장 가까운 공통 조상을 출력합니다.
풀이)
앞서 푼 콜라츠 추측과 비슷한 문제이다.
주어진 간선들이 입력하기 편하게 자식과 부모를 모두 알려주었으므로, 이를 이용해
자식 노드로부터 루트노드까지 도달하는 모든 노드를 각자의 리스트에 저장한다.
그 뒤 해당 노드가 같아지는 지점을 찾아 이를 정답으로 출력해주면 된다.
앞 인덱스부터 같은 번호를 찾게되면 O(n^2)의 시간 복잡도를 가지게 되므로,
거꾸로 생각해, 반대로 뒤에서부터 달라지는 지점을 찾게 되면 빠른 시간내에 해당 지점을 찾을 수 있다.
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
27
28
29
30
31
32
33
|
import sys
T = int(sys.stdin.readline())
for _ in range(T):
n = int(sys.stdin.readline())
# 부모 자식관계가 모두 주어지므로 1차원 배열로 진행한다.
par = [0] * (n + 1)
for i in range(n - 1):
a, b = map(int, sys.stdin.readline().strip().split())
# 부모자식관계
par[b] = a
x, y = map(int, sys.stdin.readline().strip().split())
# 두 숫자가 처음부터 같은 조상을 가졌을 수도 있으므로, 나올 수 없는
# 조상노드를 미리 입력해놓았다.
par_a = [-1]
while x:
par_a.append(x)
x = par[x]
par_b = [-2]
while y:
par_b.append(y)
y = par[y]
# 뒤에서부터 달라지는 지점 찾기
for i in range(-1, -10000, -1):
if par_a[i] != par_b[i]:
break
print(par_a[i + 1])
|
cs |
출처 : https://www.acmicpc.net/problem/3584
3584번: 가장 가까운 공통 조상
루트가 있는 트리(rooted tree)가 주어지고, 그 트리 상의 두 정점이 주어질 때 그들의 가장 가까운 공통 조상(Nearest Common Anscestor)은 다음과 같이 정의됩니다. 두 노드의 가장 가까운 공통 조상은, 두
www.acmicpc.net
'Develop > 백준 (python)' 카테고리의 다른 글
[백준] 16401번: 과자 나눠주기 (python) (0) | 2022.05.08 |
---|---|
[백준] 1758번: 알바생 강호 (python) (0) | 2022.05.08 |
[백준] 6615번: 콜라츠 추측 (python) (0) | 2022.04.27 |
[백준] 15900번: 나무 탈출 (python) (0) | 2022.04.26 |
[백준] 6064번: 카잉 달력 (python) (0) | 2022.04.18 |