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

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

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

 

 

 

문제 해결

• LCA (Low Common Ancestor)알고리즘
• 최소 공통 조상을 찾는 알고리즘은 트리문제에서 자주나오는 문제이다.
• 무조건 공통 조상은 있으므로 각 노드에서 루트로 올라가는 길을 정리하여 루트부터 다시 내려가면서 서로 갈라지는 지점을 찾으면 된다. 갈라지기 전에 가장 가까운 공통 조상이다!

CODE

import sys
input = sys.stdin.readline

def find(x,y):
    x_parent = [x]
    y_parent = [y]

    while root[x] != x :
        x_parent.append(root[x])
        x = root[x]
    while root[y] != y:
        y_parent.append(root[y])
        y = root[y]
    x_level = len(x_parent)-1
    y_level = len(y_parent)-1

    while x_parent[x_level] == y_parent[y_level]:
        x_level -= 1
        y_level -= 1
    return x_parent[x_level+1]
if __name__=='__main__':
    T = int(input())
    for _ in range(T):
        N = int(input())
        root = [i for i in range(N+1)]
        for _ in range(N-1):
            P, C = map(int, input().split())
            root[C] = P
        c1, c2 = map(int, input().split())
        answer = find(c1,c2)
        print(answer)