백준 #3584 가장 가까운 공통 조상

코드

import sys
# sys.stdin = open("input.txt")
input = sys.stdin.readline
sys.setrecursionlimit(10**6)


def dfs(node, depth):
    d[node] = depth
    for nxt in graph[node]:
        dfs(nxt, depth + 1)
    return

def lca(a, b):
    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


T = int(input())
for _ in range(T):
    n = int(input())
    graph = [[] for _ in range(n + 1)]
    d = [0] * (n + 1)
    parent = [0] * (n + 1)
    for _ in range(n - 1):
        p, c = map(int, input().split())
        parent[c] = p
        graph[p].append(c)

    root = 0

    for i in range(1, n + 1):
        if parent[i] == 0:
            root = i
            break
    dfs(root, 0)
    a, b = map(int, input().split())
    print(lca(a, b))

풀이

전형적인 LCA(Lowest Common Ancestor) 문제이다.

두 노드의 공통 조상중에서 depth가 가장 깊은 조상을 찾는 문제다!

알고리즘 동작과정은 다음과 같다.

1. 모든 노드에 대한 depth를 계산
2. 최소 공통 조상을 찾을 두 노드를 확인
   1. 먼저 두 노드의 depth가 같도록 거슬러 올라간다
   2. 두 노드의 depth가 같아졌다면 부모가 같아질 때까지 거슬러 올라간다.

이 문제에 대해서는 root노드가 안나와있지만 parent 배열의 값이 0인 노드가 root노드가 되도록 자식과 부모 관계에 대한 정보를 주었다.

root노드를 시작으로 dfs함수를 실행하여 depth를 계산한 뒤에 lca함수를 통해 공통조상을 찾아주면된다!