[baekjoon] 백준 3584번(파이썬): 가장 가까운 공통 조상

문제

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

알고리즘

- 각 노드의 부모 노드를 저장한다.

- 공통 조상을 구하려는 두 노드는 따로 저장하여 두 노드의 부모 노드들을 찾는다.

- 두 노드의 부모 노드를 레벨별로 비교하여 제일 마지막에 같았던 부모 노드를 구한다.

- 제일 마지막에 같았던 부모 노드가 가장 가까운 공통 조상 노드가 된다.

코드

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):
        a, b = map(int, sys.stdin.readline().split())
        parent[b] = a

    # 구하려는 두 노드를 저장
    a, b = map(int, sys.stdin.readline().split())
    target_a = [a]
    target_b = [b]

    # 구하려는 두 노드의 부모 노드들을 저장
    while parent[a]:
        target_a.append(parent[a])
        a = parent[a]

    while parent[b]:
        target_b.append(parent[b])
        b = parent[b]

    # 두 노드의 루트 노드부터 확인하기 위해 레벨을 맞춘다.
    target_a_level = len(target_a) - 1
    target_b_level = len(target_b) - 1

    # 두 노드의 공통 조상을 찾는다.
    # 두 노드의 루트 노드가 다를 때까지 반복
    while target_a[target_a_level] == target_b[target_b_level]:
        target_a_level -= 1
        target_b_level -= 1

    # 이전 레벨의 노드가 공통 조상 노드
    print(target_a[target_a_level + 1])

github

GitHub - junjange/CodingTest: 내가 푼 코딩 테스트 문제와 해결법