[백준] 3584번: 가장 가까운 공통 조상 / Python / 그래프 탐색
가장 가까운 공통 조상
문제
루트가 있는 트리(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 이하의 정수로 이름 붙여집니다.
테스트 케이스의 마지막 줄에 가장 가까운 공통 조상을 구할 두 노드가 주어집니다.
출력
각 테스트 케이스 별로, 첫 줄에 입력에서 주어진 두 노드의 가장 가까운 공통 조상을 출력합니다.
풀이 방법
- parent 리스트에 각 노드의 부모를 저장해둔다.
- 공통 조상을 찾으려는 노드 a, b의 부모들을 parent에서 모두 거슬러 올라가며 a_parents, b_parents에 저장한다.
- a_parents, b_parents 모두 맨 마지막에는 루트 노드가 저장되어 있다. 뒤에서부터 탐색하면서 서로 부모가 달라지는 지점 바로 직전이 가장 가까운 공통 조상이 된다.
t = int(input())
for _ in range(t):
n = int(input())
parent = [0] * (n + 1) # 각 노드의 부모 저장
for _ in range(n - 1):
i, j = map(int, input().split())
parent[j] = i
a, b = map(int, input().split())
a_parents, b_parents = [0, a], [0, b] # a와 b가 부모-자식 관계일 수 있으니 인덱스 에러가 나지 않도록 0을 넣어주자
while parent[a]:
a_parents.append(parent[a])
a = parent[a]
while parent[b]:
b_parents.append(parent[b])
b = parent[b]
# 뒤에서부터 거꾸로 탐색하며 가장 가까운 공통 조상을 찾자
i = 1
while a_parents[-i] == b_parents[-i]:
i += 1
print(a_parents[-i + 1])
Author And Source
이 문제에 관하여([백준] 3584번: 가장 가까운 공통 조상 / Python / 그래프 탐색), 우리는 이곳에서 더 많은 자료를 발견하고 링크를 클릭하여 보았다 https://velog.io/@dhelee/백준-3584번-가장-가까운-공통-조상-Python-그래프-탐색저자 귀속: 원작자 정보가 원작자 URL에 포함되어 있으며 저작권은 원작자 소유입니다.
우수한 개발자 콘텐츠 발견에 전념 (Collection and Share based on the CC Protocol.)