[백준] 3584번: 가장 가까운 공통 조상 (Python/파이썬) - tree 문제

https://www.acmicpc.net/problem/3584

3584번: 가장 가까운 공통 조상

1. 입력받은 값으로 트리를 구성한다.

python의 defaultdict을 사용했다. 어처피 간선 정보는 자식노드 - 부모노드로 N-1개 주어지므로 리스트가 아니라 default(int) 로 value 값을 저장한다. 

2. 재귀함수 (dfs)로 루트까지 가는 경로를 구하는 함수 작성

3. 각각의 노드에서 루트까지 가는 경로를 구한다. 

4. 경로 중에서 가장 가까운 부모 노드를 찾는다. 

from collections import defaultdict
import sys 
sys.setrecursionlimit(10**9)
T = int(input())

# dfs 로 부모 찾기 
def dfs(now, route, tree):
    if tree[now] == 0:
        route.append(now)
        return route 
    p_node = tree[now]
    route.append(now)
    return dfs(p_node, route, tree)

for _ in range(T):
    N = int(input()) # 1 ~ N
    tree = defaultdict(int)

    for _ in range(N-1):
        a, b = map(int, input().split()) # a가 b의 부모 
        tree[b] = a
    x, y = map(int, input().split())

    route_x = dfs(x, [], tree)
    route_y = dfs(y, [], tree)
    answer = 0
    flag = True 
    for node1 in route_x:
        for node2 in route_y:
            if node1 == node2:
                answer = node1
                flag = False 
                break 
        if not flag:
            break 

    # 공통 조상 찾기 
    print(answer)