[백준 3584번] 가장 가까운 공통 조상 (python)

문제

루트가 있는 트리(rooted tree)가 주어지고, 그 트리 상의 두 정점이 주어질 때 그들의 가장 가까운 공통 조상(Nearest Common Anscestor)은 다음과 같이 정의됩니다.

• 두 노드의 가장 가까운 공통 조상은, 두 노드를 모두 자손으로 가지면서 깊이가 가장 깊은(즉 두 노드에 가장 가까운) 노드를 말합니다.

예를 들어  15와 11를 모두 자손으로 갖는 노드는 4와 8이 있지만, 그 중 깊이가 가장 깊은(15와 11에 가장 가까운) 노드는 4 이므로 가장 가까운 공통 조상은 4가 됩니다.

루트가 있는 트리가 주어지고, 두 노드가 주어질 때 그 두 노드의 가장 가까운 공통 조상을 찾는 프로그램을 작성하세요

 

기록

(트리 4일차) 풀 수 있는 방법이 많을 것 같은데, 루트 노드를 모르니까 위에서부터 재귀적으로 탐색하는건 어려울 것 같아 주어진 노드부터 올라가는 방법으로 구현하려고 했다.

 

코드

from sys import stdin
from collections import defaultdict

T = int(stdin.readline())
for i in range(T):

    # 변수 초기화
    N = int(stdin.readline())
    tree_up = defaultdict(list)
    for j in range(N-1):
        a, b = list(map(int, stdin.readline().split()))
        tree_up[b] = a
    a, b = list(map(int, stdin.readline().split()))

    # a 루트노드들 배열에 저장
    a_roots = []
    while a in tree_up:
        a_roots.append(a)
        a = tree_up[a]

    # b 루트노드로 올라가면서 a 루트노드 배열에 있는지 확인
    while b in tree_up:
        if b in a_roots :
            break
        b = tree_up[b]

    print(b)

주어진 노드 a b 중 a부터 루트노드까지의 경로를 저장하고, 그 다음 b부터 루트노드까지 탐색하며 a경로와 겹치는 노드를 찾으면 출력하고 끝내도록 구현