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

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

# 가장 가까운 공통 조상

def find_parent(parent, x):
    result = [x]
    while parent[x]:
        result.append(parent[x])
        x = parent[x]
    return result


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

    x, y = map(int, input().split())
    # 각 부모 리스트 정의
    x_parent = find_parent(parent, x)
    y_parent = find_parent(parent, y)

    # 깊이 맞춰주기
    i, j = 0, 0
    if len(x_parent) > len(y_parent):
        i = len(x_parent) - len(y_parent)
    else:
        j = len(y_parent) - len(x_parent)

    # 같은 깊이에서 최소 공통 조상 찾기
    while x_parent[i] != y_parent[j]:
        i += 1
        j += 1
    print(x_parent[i])

 

최소 공통 조상 (LCA)
테스트 케이스만큼 진행
1. parent 리스트에 각각 부모를 기록, x와 y 입력
2. find_parent : 자기 자신으로부터 거슬러 올라가 깊이가 0인 부모까지 기록한 리스트 반환
    - x와 y에 대해서 각각 진행
3. 깊이 맞춰주기 (i와 j는 각각 x_parent와 y_parent의 시작 인덱스)
    - 두 깊이가 같아지도록 더 index값을 조정
4. 최소 공통 조상 찾기
    - 두 부모의 값이 같아질 때까지 탐색
5. 출력

 

LCA라 하면 깊이를 먼저 맞춰주고 나서 거슬러 올라가며 같은 부모를 찾는 방법이다.

이 문제는 간선이 무작위로 주어져서 리스트를 이용해서 풀었다.