(3584)가장 가까운 공통 조상 - 참고 해결

(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 이하의 정수로 이름 붙여집니다.

테스트 케이스의 마지막 줄에 가장 가까운 공통 조상을 구할 두 노드가 주어집니다.

출력

각 테스트 케이스 별로, 첫 줄에 입력에서 주어진 두 노드의 가장 가까운 공통 조상을 출력합니다.

처음에는 브루트 포스하게 각각의 조상을 2중 for문을 사용해서 탐색하려 하였으나 시간 초과 발생.

그래서 찾아보니 LCA(최소 공통 조상) 알고리즘이 있었다.

해당 방법은 각각의 조상들을 다 찾고 루트 부터 비교하면서 내려오다가 다른 지점의 바로 전이 최소 공통 조상이라는 알고리즘이였다.

원래 했던 방법에서 각 조상을 찾고 루트부터 내려오는 알고리즘을 추가하였다.

import sys T = int(sys.stdin.readline().strip()) # 조상 찾기 def listpar(node): plist = [] while node != 0: plist.append(node) node = tree[node] return plist for _ in range(T): N = int(sys.stdin.readline().strip()) tree = [0 for _ in range(N+1)] # 트리 그리기 for _ in range(1,N): A, B = map(int,sys.stdin.readline().strip().split()) tree[B] = A # 각각의 시작을 저장 st, ed = map(int,sys.stdin.readline().strip().split()) # 각각의 조상 리스트 # 처음 0은 어느 한 리스트의 시작점이 공통 조상일 때를 위해서 A_list = [0] + listpar(st) B_list = [0] + listpar(ed) # 루트 부터 찾기 위해서 cnt 사용 cnt = 1 while A_list[-cnt] == B_list[-cnt]: cnt += 1 # 분기점 바로 전이 최소 공통 print(A_list[-cnt+1])

from http://h-study.tistory.com/140 by ccl(A) rewrite - 2021-09-23 19:26:42