백준 3584번: 가장 가까운 공통 조상 (Python)

접근

문제에 있는 설명과 같이 가장 가까운 공통 조상 (LCA, lowest common ancestor) 알고리즘을 이용하여 풀 수 있다.

주어진 트리들을 이용하여 부모를 구할 수 있도록 저장해준 후, 마지막으로 비교해야 하는 a 와 b 에 대하여 그 부모들을 모두 리스트로 순서대로 저장한다. 두 리스트 모두 마지막 요소를 루트 노드로 가지고 있을 것이다. 그러면 루트 노드부터 시작하여 아래로 내려오면서 비교하여 같지 않은 노드가 나올 때까지 탐색하면, 바로 직전 노드가 가장 가까운 공통 조상이게 된다.

LCA 알고리즘 개념 및 설명: LCA(Lowest Common Ancestor) 알고리즘

LCA(Lowest Common Ancestor) 알고리즘

코드

import sys

t = int(sys.stdin.readline())
for _ in range(t):
    n = int(sys.stdin.readline())
    parent = [0] * (n + 1)
    for __ in range(n - 1):
        p, c = map(int, sys.stdin.readline().split())
        parent[c] = p
    a, b = map(int, sys.stdin.readline().split())
    a_list = [0, a]
    b_list = [0, b]
    while parent[a]:
        a_list.append(parent[a])
        a = parent[a]
    while parent[b]:
        b_list.append(parent[b])
        b = parent[b]
    cnt = 1
    while a_list[-cnt] == b_list[-cnt]:
        cnt += 1
    print(a_list[-cnt + 1])

더 생각해 볼 것?

...

코드나 내용 관련 조언, 부족한 점 및 질문 언제든 환영합니다!