최소 공통 조상(Lowest Common Acestor, LCA) 알고리즘 10분 정복

Purple·2022년 8월 18일

python

자료구조 및 알고리즘 python

목록 보기

28/28

이것이 취업을 위한 코딩테스다 with 파이썬(이코테 2021) 유튜브 영상을 보면서 공부한 자료입니다.
https://www.youtube.com/watch?v=m-9pAwq1o3w&list=PLRx0vPvlEmdAghTr5mXQxGpHjWqSz0dgC

최소 공통 조상(Lowest Common Ancestor): 기초 문제

기본적인 최소 공통 조상(LCA) 알고리즘

최소 공통 조상 찾기 알고리즘은 다음과 같다.

기본적인 최소 공통 조상(LCA) 알고리즘

import sys
# 런타임 오류를 피하기
sys.setrecursionlimit(int(1e5))
n = int(input())

# 부모 노드 정보
parent = [0] * (n + 1)
# 각 노드까지의 깊이
d = [0] * (n + 1)
# 각 노드의 깊이가 계산되었는지 여부
c = [0] * (n + 1)
# 그래프(graph) 정보
graph = [[] for _ in range(n + 1)]

for _ in range(n - 1):
    a, b = map(int, input().spli())
    graph[a].append[b]
    graph[b].append[a]

# 루트 노드부터 시작하여 깊이(depth)를 구하는 함수
def dfs(x, depth):
    c[x] = True
    d[x] = depth
    for y in graph[x]:
        # 이미 깊이를 구했다면 넘기기
        if c[y]:
            continue
        parent[y] = x
        dfs(y, depth + 1)

# A와 B의 최소 공통 조상을 찾는 함수
def lca(a, b):
    # 먼저 깊이(depth)가 동일하도록
    while d[a] != d[b]:
        if d[a] > d[b]:
            a = parent[a]
        else:
            b = parent[b]
    # 노드가 같아지도록
    while a != b:
        a = parent[a]
        b = parent[b]
    return a

# 루트 노드는 1번 노드
dfs(1, 0)

m = int(input())

for i in range(m):
    a, b = map(int, input().split())
    print(lca(a, b))