[백준] 3584번 - 가장 가까운 공통 조상 Python, Java

Tuna·2022년 3월 10일

LCA tree 그래프 백준 트리

Tree

목록 보기

10/13

문제

루트가 있는 트리(rooted tree)가 주어지고, 그 트리 상의 두 정점이 주어질 때 그들의 가장 가까운 공통 조상(Nearest Common Anscestor)은 다음과 같이 정의됩니다.

두 노드의 가장 가까운 공통 조상은, 두 노드를 모두 자손으로 가지면서 깊이가 가장 깊은(즉 두 노드에 가장 가까운) 노드를 말합니다.

예를 들어 15와 11를 모두 자손으로 갖는 노드는 4와 8이 있지만, 그 중 깊이가 가장 깊은(15와 11에 가장 가까운) 노드는 4 이므로 가장 가까운 공통 조상은 4가 됩니다.

루트가 있는 트리가 주어지고, 두 노드가 주어질 때 그 두 노드의 가장 가까운 공통 조상을 찾는 프로그램을 작성하세요

입력

첫 줄에 테스트 케이스의 개수 T가 주어집니다.

각 테스트 케이스마다, 첫째 줄에 트리를 구성하는 노드의 수 N이 주어집니다. (2 ≤ N ≤ 10,000)

그리고 그 다음 N-1개의 줄에 트리를 구성하는 간선 정보가 주어집니다. 한 간선 당 한 줄에 두 개의 숫자 A B 가 순서대로 주어지는데, 이는 A가 B의 부모라는 뜻입니다. (당연히 정점이 N개인 트리는 항상 N-1개의 간선으로 이루어집니다!) A와 B는 1 이상 N 이하의 정수로 이름 붙여집니다.

테스트 케이스의 마지막 줄에 가장 가까운 공통 조상을 구할 두 노드가 주어집니다.

출력

각 테스트 케이스 별로, 첫 줄에 입력에서 주어진 두 노드의 가장 가까운 공통 조상을 출력합니다.

예제 입력 1

예제 출력 1

4
3

풀이

Python

import sys
input = sys.stdin.readline
sys.setrecursionlimit(int(1e5)) # 런타임 오류 피하기
LOG = 21 # 2^20 = 1,000,000
t = int(input().rstrip())

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

# 전체 부모 관계를 설정하는 함수
def set_parent(root):
    dfs(root,0)
    for i in range(1, LOG):
        for j in range(1,n+1):
            parent[j][i] = parent[parent[j][i-1]][i-1]


# A와 B의 최소 공통 조상을 찾는 함수
def lca(a,b):
    # b가 더 깊도록 설정
    if d[a]>d[b]:
        a,b = b,a
    # 먼저 깊이(depth)가 동일하도록
    for i in range(LOG-1,-1,-1):
        if d[b]-d[a]>=(1<<i):
            b = parent[b][i]
    # 부모가 같아지도록
    if a == b:
        return a
    for i in range(LOG-1,-1,-1):
        # 조상을 향해 거슬러 올라가기
        if parent[a][i] != parent[b][i]:
            a = parent[a][i]
            b = parent[b][i]
    # 이후에 부모가 찾고자 하는 조상
    return parent[a][0]

for _ in range(t):
    n = int(input().rstrip())

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

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

    start = 0
    for i in range(1,n+1):
        if parent[i][0] == 0:
            start = i

    set_parent(start)

    a,b = map(int, input().rstrip().split())
    print(lca(a,b))