문제 보기 · Level 5 · 2017 카카오코드 예선 · 정답률 2% · 푼 사람 135명 (2026-09-30 기준)1

문제

뿌리가 1번인 나무 두 개가 주어진다. 자식의 순서와 이름은 따지지 않는다. 각 나무의 뿌리를 포함하는 부분 나무 가운데 두 나무에 모두 들어 있는 모양(공통부분)을 찾는다. 가장 큰 공통부분의 노드 수를 돌려준다.

  • 1 ≤ n1, n2 ≤ 100
  • g1, g2의 각 줄은 이어진 두 노드다. 둘 중 어느 쪽이 부모인지는 정해져 있지 않다

풀이

막히면 한 단계씩 펼친다.

필요한 개념

트리 DP: “노드 u와 v를 맞춰 놓았을 때 그 아래에서 맞출 수 있는 가장 큰 크기”를 자식부터 채운다. u의 자식들과 v의 자식들을 겹치지 않게 짝지어 값의 합을 최대로 하는 일은 점수가 있는 이분 매칭(헝가리안 방법)이다.

1단계 · 작은 예로 손으로 풀기

문제의 예시를 뿌리부터 그리면 이렇다.

나무 1:  1 ─┬─ 3 ─┬─ 2          나무 2:  1 ─┬─ 5 ─┬─ 6
            │     ├─ 4                      │     └─ 9 ── 8
            │     └─ 6                      └─ 3 ── 7 ─┬─ 4
            └─ 5 ── 7 ── 8                                └─ 2

뿌리끼리 맞춘 뒤, 나무 1의 자식 {3, 5}와 나무 2의 자식 {5, 3}을 짝짓는다.

  • 나무 1의 3(잎 셋)과 나무 2의 5(잎 하나, 한 줄 둘): 잎 둘을 맞춰 3개.
  • 나무 1의 5(한 줄 셋)와 나무 2의 3(한 줄 셋에서 갈라짐): 3개.

두 짝을 합쳐 1 + 3 + 3 = 7이다. 반대로 3–3, 5–5로 짝지으면 1 + 2 + 3 = 6이라 짝을 잘 골라야 한다.

2단계 · 가장 단순한 방법과 그 속도

뿌리를 포함하는 부분 나무를 모두 만들어 모양끼리 비교한다. 별 모양 나무(뿌리에 잎 99개)만 해도 잎을 고르는 방법이 \(2^{99}\)가지라 어림없다.

3단계 · 핵심 아이디어
  • 두 노드를 맞추는 값: dp[u][v] = 나무 1의 u와 나무 2의 v를 맞춰 놓았을 때, 그 아래에서 맞출 수 있는 공통부분의 가장 큰 크기다. 답은 dp[1][1]이다.
  • 자식끼리 짝짓기: u와 v를 맞추면 u의 자식 하나는 v의 자식 하나와만 맞출 수 있다. 자식의 순서는 따지지 않으니 어느 자식과 짝지어도 된다. 짝 (c, d)를 고르면 그 아래는 dp[c][d]만큼 맞춘다. 서로 다른 자식 아래는 겹치지 않아 따로 가장 좋게 고르면 된다. 그래서 dp[u][v] = 1 + (u의 자식과 v의 자식을 겹치지 않게 짝지어 얻는 dp 값의 합의 최댓값)이다.
  • 점수가 있는 짝짓기: 짝마다 점수 dp[c][d]가 달라 개수만 세는 이분 매칭으로는 안 된다. 점수 합을 최대로 하는 헝가리안 방법을 쓴다. 점수가 모두 1 이상이라, 작은 쪽 자식이 모두 짝을 얻는 것이 늘 가장 좋다.
  • 채우는 순서: dp[c][d]가 dp[u][v]보다 먼저 있어야 하니, 두 나무 모두 자식이 먼저인 순서로 돈다.
4단계 · 코드 흐름
  1. 각 나무를 양방향으로 잇고, 뿌리 1에서 스택으로 내려가며 부모와 자식을 정한다. 내려간 순서를 뒤집으면 자식이 먼저다.
  2. 나무 1의 노드 u, 나무 2의 노드 v를 자식이 먼저인 순서로 돈다.
  3. 표 w[i][j] = dp[u의 i번째 자식][v의 j번째 자식]을 만들고, dp[u][v] = 1 + best_matching(w).
  4. dp[1][1]을 돌려준다.
5단계 · 파이썬 코드 
def best_matching(w):
    """행과 열을 겹치지 않게 짝지어 얻는 값의 합의 최댓값(헝가리안 방법)."""
    if not w or not w[0]:
        return 0
    if len(w) > len(w[0]):
        w = [list(col) for col in zip(*w)]     # 행이 열보다 많지 않게 돌린다
    n, m = len(w), len(w[0])
    INF = float("inf")
    u, v = [0] * (n + 1), [0] * (m + 1)        # 잠재값
    match, way = [0] * (m + 1), [0] * (m + 1)
    for i in range(1, n + 1):                  # 행을 하나씩 짝에 넣는다
        match[0], j0 = i, 0
        minv, used = [INF] * (m + 1), [False] * (m + 1)
        while True:                            # 가장 싸게 늘리는 길을 찾는다
            used[j0] = True
            i0, delta, j1 = match[j0], INF, 0
            for j in range(1, m + 1):
                if not used[j]:
                    cur = -w[i0 - 1][j - 1] - u[i0] - v[j]   # 값을 비용(−값)으로
                    if cur < minv[j]:
                        minv[j], way[j] = cur, j0
                    if minv[j] < delta:
                        delta, j1 = minv[j], j
            for j in range(m + 1):
                if used[j]:
                    u[match[j]] += delta
                    v[j] -= delta
                else:
                    minv[j] -= delta
            j0 = j1
            if match[j0] == 0:
                break
        while j0:                              # 찾은 길을 따라 짝을 바꾼다
            j1 = way[j0]
            match[j0] = match[j1]
            j0 = j1
    return sum(w[match[j] - 1][j - 1] for j in range(1, m + 1) if match[j])

def children_lists(n, g):
    adj = [[] for _ in range(n + 1)]
    for p, q in g:
        adj[p].append(q)
        adj[q].append(p)
    kids = [[] for _ in range(n + 1)]
    order, seen, stack = [], [False] * (n + 1), [1]
    seen[1] = True
    while stack:
        x = stack.pop()
        order.append(x)
        for c in adj[x]:
            if not seen[c]:
                seen[c] = True
                kids[x].append(c)
                stack.append(c)
    return kids, order[::-1]                   # 자식이 먼저인 순서

def solution(n1, g1, n2, g2):
    kids1, order1 = children_lists(n1, g1)
    kids2, order2 = children_lists(n2, g2)
    dp = [[0] * (n2 + 1) for _ in range(n1 + 1)]
    for a in order1:
        for b in order2:
            w = [[dp[c][d] for d in kids2[b]] for c in kids1[a]]
            dp[a][b] = 1 + best_matching(w)
    return dp[1][1]
  • children_lists: 입력 줄의 두 값 중 어느 쪽이 부모인지 모르니 양방향으로 잇고, 뿌리에서 먼저 닿는 쪽을 부모로 정한다. 트리에서는 뿌리에서 각 노드로 가는 길이 하나뿐이고, 그 길의 바로 앞 노드가 부모다. 다른 이웃은 모두 이 노드를 거쳐야 닿으므로 먼저 닿는 쪽이 늘 부모다.
  • best_matching: 개념 문서의 짝짓기에 점수를 붙인 판이다. 잠재값 u, v를 두고, 행을 하나씩 넣을 때마다 비용이 가장 적게 드는 길로 짝을 바꾼다. 점수를 최대로 하려고 점수에 −를 붙여 비용을 최소로 한다.
  • 자식이 없으면 표가 비어 best_matching이 0을 돌려준다. 그래서 잎끼리는 dp = 1이다.
6단계 · 실행 추적

1단계의 예다. 나무 1의 자식 3, 5와 나무 2의 자식 5, 3 사이의 dp 값이다.

  나무 2의 5 나무 2의 3
나무 1의 3 3 2
나무 1의 5 3 3
  • dp[3][5] = 1 + (잎 셋과 {잎 6, 9 – 8}의 짝: 1 + 1) = 3, dp[3][3] = 1 + (잎 셋과 {7}의 짝: 1) = 2.
  • dp[5][5] = 1 + (7 – 8과 9 – 8의 짝: 2) = 3, dp[5][3] = 1 + (7 – 8과 7 – {4, 2}의 짝: 2) = 3.
  • 짝은 (3, 5)와 (5, 3)을 고를 때 3 + 3 = 6으로 가장 크다. dp[1][1] = 1 + 6 = 7이다.
7단계 · 복잡도와 흔한 실수

노드 쌍이 n1 × n2 = 1만 개이고, 쌍마다 자식 수 크기의 표에 헝가리안 방법을 쓴다. 한 나무의 자식 수를 모두 더하면 노드 수보다 하나 적어(간선 수) 전체가 작다. 노드 100개짜리 입력 넷(별 둘, 한 줄 둘, 별과 한 줄, 무작위 둘)을 합쳐 0.1초가 안 걸렸다.

  • 자식끼리 짝을 지을 때 값이 큰 칸부터 욕심껏 고른다. 표 [[2, 3], [3, 3]]에서 아래 오른쪽 3을 먼저 고르면 남은 칸이 2라 5다. 위 오른쪽과 아래 왼쪽을 고르면 6이다. 표 [[3, 2], [2, 0]]도 3을 먼저 고르면 3이지만, 2 + 2 = 4가 크다.
  • 자식을 주어진 순서대로만 맞춘다. 자식 순서는 따지지 않는 문제다.
  • 입력 줄의 앞 값을 부모로 읽는다. 예시의 [3, 1]처럼 자식이 앞에 올 수 있다.
검증: 문제의 예시와 6단계 표의 dp 값을 코드로 확인했다. 헝가리안 방법은 무작위 표 2,000개(5 × 5 이하)에서 순열 전부와 같았다. 무작위 나무 쌍 1,500개(노드 9개 이하)에서 “뿌리를 포함한 부분 나무의 모양을 모두 적어 비교하는” 풀이와 결과가 같았다. 노드 100개 입력의 시간도 쟀다 — 34_pg1834_p1.py

  1. 프로그래머스 스쿨, “신비로운 유적 탐험” (https://school.programmers.co.kr/learn/courses/30/lessons/1834), 2026-10-01 조회. ↩