[백준] 3584번 가장 가까운 공통 조상 - 파이썬/트리

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

import sys
sys.setrecursionlimit(10**6)

T = int(input())

for t in range(T):


    N = int(input())

    graph = [ [] for _ in range(N+1) ]

    for i in range(N-1):
        A,B = map(int,input().split())

        graph[B].append(A)



    check1,check2 = map(int,input().split())

    def dfs(x,root):

        if graph[x]:

            root.append(graph[x][0])

            dfs(graph[x][0],root)

    root1=[check1]
    root2=[check2]

    dfs(check1,root1)

    dfs(check2,root2)

    while True:

        if not root1 or not root2:
            print(temt)
            break

        elem1 = root1.pop()
        elem2 = root2.pop()

        if elem1==elem2:
            temt = elem1
            continue
        else:
            print(temt)
            break

graph에 부모 노드를 기록했다.

그리고 재귀함수로 타고올라가면서 그 루트를 저장했다.

공통 조상을 구해야할 노드 C와 D가 주어지면

C의 루트는 [16,10,4,8]

D의 루트는 [7,6,4,8] 이런 식으로 나오는데

뒷열부터 하나씩 지워가면서 두 값이 달라지는 케이스 바로 전 숫자를 출력하면 된다.

중요한것은 자기 자신도 정답이 될 수 있다는 경계값을 알아내는 것이였다.

예를 들면 이러한 트리에서 3,5의 공통 조상은 2가 아닌 3이다.