문제 바로가기
문제:
루트가 있는 트리(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 이하의 정수로 이름 붙여집니다. 테스트 케이스의 마지막 줄에 가장 가까운 공통 조상을 구할 두 노드가 주어집니다.
출력:
각 테스트 케이스 별로, 첫 줄에 입력에서 주어진 두 노드의 가장 가까운 공통 조상을 출력합니다.
풀이 :
import sys
sys.stdin = open('/Users/song/Desktop/Python/Python/h.txt', 'r')
# 부모 찾기 위한 함수
def find_parent(parent, x):
# 자기자신은 자기가 부모
result = [x]
# x의 부모가 존재 하는 동안
while parent[x]:
# 부모를 넣어주고
result.append(parent[x])
# 부모의 부모를 찾기위해 x를 부모로 바꿔준다.
x = parent[x]
# 다 찾았으면 그대로 결과값 리턴
return result
T = int(input())
for _ in range(T):
N = int(input())
# 부모 처음은 자기자신이 부모이다.
parent = [0 for _ in range(N+1)]
for _ in range(N-1):
x, y = map(int,sys.stdin.readline().split(" "))
# y의 부모는 x
parent[y] = x
# 마지막 찾을 노드
a, b = map(int, input().split())
# 자기 자신 포함 부모 찾기
lst_a = find_parent(parent,a)
lst_b = find_parent(parent,b)
x, y = 0,0
# lst_a의 깊이가 더 깊은 경우 b만큼 길이만 필요하다.
if len(lst_a) > len(lst_b):
lst_a = lst_a[-len(lst_b):]
else:
lst_b = lst_b[-len(lst_a):]
# 잘린거 기준으로 앞에서 부터 비교
depth = 0
while lst_a[depth] != lst_b[depth]:
depth += 1
print(lst_a[depth])
과거의 유니온_파인드 알고리즘을 공부해서 나쁘지 않았다고 생각한다.
그래도 헷갈린다.
설명은 주석을 참고하길 바란다.
댓글