[Python/파이썬] 백준 3584번: 가장 가까운 공통 조상

문제

 

풀이

백준 LCA 문제와 동일한 줄 알았는데 아니었다.

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

11437번: LCA

 

차이점은 LCA의 경우 양방향 간선으로 입력이 주어지지만, 가장 가까운 공통 조상의 경우 단방향으로 간선이 주어진다.

또한 LCA는 루트 노드가 1로 고정되지만, 가장 가까운 공통 조상의 경우 루트 노드를 직접 구해야 한다.

 

코드

import sys
sys.setrecursionlimit(10**9)
input = sys.stdin.readline


def dfs(x, depth):
    visited[x] = True
    d[x] = depth
    for child in graph[x]:
        if visited[child]:  continue
        dfs(child, depth + 1)
        
t = int(input())

for _ in range(t):
    n = int(input())
    graph = [[] for _ in range(n + 1)]
    visited = [False] * (n + 1)
    parent = [0] * (n + 1)
    d = [0] * (n + 1)
    
    for _ in range(n - 1):
        a, b = map(int, input().split())
        graph[a].append(b)
        parent[b] = a
    
    for i in range(1, n + 1):
        if parent[i] == 0:
            dfs(i, 0)
            break
    
    a, b = map(int, input().split())
    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]
    
    print(a)

 

마무리

LCA도 어느 정도 마스터한 듯 싶다. ㅎㅎ