[Python]최소공통조상 백준 3584

   문제

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

최소공통조상(Lowest common ancestor)

LCA(최소공통조상)은 영어 해석 그대로 최소 공통 조상을 찾는 알고리즘이고, 두 정점 

u, v(혹은 a, b)에서 가장 가까운 공통 조상을 찾는 과정을 말한다.

정확히 무엇을 뜻하는 지는 아래 사이트를 통해 보면 쉽게 알 수 있다.

https://www.crocus.co.kr/660

문제 해결은 각 노드의 부모노드들을 모두 저장한뒤 루트노드부터 차례대로 내려오며 

비교하여 같지 않은 노드가 나올때까지 반복한다. 처음으로 같지않은 노드가 나왔을때 

그 노드의 부모가 최소공통조상이라고 볼 수 있다.

import sys
T=int(sys.stdin.readline())
for _ in range(T):
    N=int(sys.stdin.readline())
    p_list=[0 for _ in range(N+1)]#각 노드의 부모노드 저장
    for _ in range(N-1):
        p,c=map(int,sys.stdin.readline().split())
        p_list[c]=p#부모 노드 저장
 
    a,b=map(int,sys.stdin.readline().split())
    a_parent=[a]
    b_parent=[b]
    #각노드의 부모노드가 루트일때까지 모두 저장
    while p_list[a]:
        a_parent.append(p_list[a])
        a=p_list[a]
 
    while p_list[b]:
        b_parent.append(p_list[b])
        b=p_list[b]
 
    #같은 레벨로 맞추고 부모노드 같은거 찾기
 
 
    a_level=len(a_parent)-1
    b_level=len(b_parent)-1
    # 루트노드부터 차례대로 비교
    while a_parent[a_level]==b_parent[b_level]:#부모노드가 같지 않을때까지
        a_level-=1
        b_level-=1
 
    print(a_parent[a_level+1])