백준 3584번 가장 가까운 공통 조상 | python | union-find

문제

링크

풀이

처음에 문제를 잘못 읽어서 입력으로 들어오는 a, b를 union 연산 하라는 줄 알았는데 알고보니 a가 b의 부모 관계였다. 따라서 유니온 파인드의 기본 풀이인 부모를 찾는 과정은 입력 자체로 바로 알 수 있으니 패스.

마지막 줄에 입력된 두 노드에 대하여 가장 가까운 공통 조상을 구하면 되는데, 이 때 먼저 입력된 노드 ta에 대해 부모 경로를 리스트에 담고 이를 tracking_ta 라고 하자.

이후 tb도 자신의 부모 경로를 거슬러 올라가며 중간에 tracking_ta 안에 있는 값과 일치하는 순간이 온다면 그것을 가장 가까운 공통 조상이라고 간주하고 출력하면 된다.

tc=int(input())
for _ in range(tc):
    n=int(input())
    parent=[0]*(n+1)
    for _ in range(n-1):
        a,b=map(int,input().split())
        parent[b]=a

    ta,tb=map(int,input().split())
    tracking_ta=[]
    # print(parent)
    while True:
        if ta==0:
            break
        tracking_ta.append(ta)
        ta=parent[ta]

    # print(tracking_ta)
    # tracking_ta=set(tracking_ta)
    while True:
        if tb in tracking_ta:
            print(tb)
            break
        tb=parent[tb]

• in 메소드의 시간복잡도를 줄이기 위해 tracking_ta의 자료형을 list 대신 set으로 변환할 수 있다 (그러나 list로 두어도 시간초과가 나지는 않았다)
• 입력된 노드부터 tracking_ta에 넣어주어야 함 (간과하면 안 됨)