트리 동형 사상 (Tree Isomorphism)

2026년 6월 24일 · 수정 2026년 6월 24일 · 📖 약 3분 · 1,105자/단어 #algorithm #tree #hashing

정의

트리 동형 사상 (Tree Isomorphism) 판정은 두 트리 T1, T2 가 구조적으로 같은지, 즉 노드 라벨을 무시했을 때 edge 연결 패턴이 동일한지 O(N) 에 확인하는 알고리즘. 주로 해시 (hash) 를 이용해 각 서브트리에 고유 값을 부여하고, 루트 해시가 같으면 isomorphic.

Aho-Hopcroft-Ullman (1974) 이 O(N log N) 알고리즘을 고안했고, 이후 O(N) 버전이 등장. PS 에서는 DFS + 정렬된 자식 해시 조합이 표준.

문제 상황과 동기

그래프 동형 (Graph Isomorphism) 은 NP-hard 미해결이지만, 트리 는 사이클 없는 연결 그래프라 O(N) 에 해결 가능.

naive (완전 탐색): 모든 노드 매칭 시도. O(N!). N=20 도 불가능.
tree iso (해시): DFS 한 번에 서브트리별 해시. O(N log N) (자식 정렬 비용) 또는 O(N) (정렬 없는 버전).

핵심 통찰: 서브트리 구조는 재귀적. 자식들의 해시를 정렬해서 병합하면 루트에서 전체 구조 캡처.

자주 등장: 트리 변환 최소 비용, 중복 서브트리 제거, 구조 비교.

시각화

핵심 아이디어

invariant: 같은 구조의 서브트리는 같은 해시.

hash(v) = combine(sorted([hash(child1), hash(child2), ...]))

리프는 공통 초기값 (예: 0 또는 1).
내부 노드는 자식 해시 배열을 정렬 후 해시 함수 적용.
순서 무관: combine([a, b]) == combine([b, a]) 보장.

충돌 최소화: 소수 base + modulo 또는 polynomial rolling hash. 실무 / PS 모두 충돌 가능성 낮음.

알고리즘

tree_hash(v, parent):
    if v is leaf:
        return 1
    child_hashes = []
    for each child u of v (u ≠ parent):
        child_hashes.append(tree_hash(u, v))
    child_hashes.sort()
    return combine(child_hashes)  // e.g., polynomial hash

is_isomorphic(T1, T2):
    h1 = tree_hash(root1, -1)
    h2 = tree_hash(root2, -1)
    return h1 == h2

combine 예시:

// polynomial rolling hash
ull combine(vector<ull>& hashes) {
    ull result = 1;
    for (auto h : hashes)
        result = result * BASE + h;
    return result;
}

구현

// 트리 동형 판정, 정렬된 자식 해시, O(N log N)
#include <bits/stdc++.h>
using namespace std;
using ull = unsigned long long;

const ull BASE = 1000000007;

map<vector<ull>, ull> memo;
ull next_id = 1;

vector<vector<int>> adj1, adj2;

ull tree_hash(int v, int parent, vector<vector<int>>& adj) {
  vector<ull> child_hashes;
  for (int u : adj[v]) {
      if (u == parent) continue;
      child_hashes.push_back(tree_hash(u, v, adj));
  }
  if (child_hashes.empty()) return 1;  // 리프
  sort(child_hashes.begin(), child_hashes.end());
  if (memo.count(child_hashes)) return memo[child_hashes];
  return memo[child_hashes] = next_id++;
}

int main() {
  int n, m; cin >> n >> m;
  adj1.resize(n); adj2.resize(m);
  for (int i = 0; i < n - 1; i++) {
      int u, v; cin >> u >> v; u--; v--;
      adj1[u].push_back(v); adj1[v].push_back(u);
  }
  for (int i = 0; i < m - 1; i++) {
      int u, v; cin >> u >> v; u--; v--;
      adj2[u].push_back(v); adj2[v].push_back(u);
  }
  if (n != m) { cout << "NO\n"; return 0; }
  ull h1 = tree_hash(0, -1, adj1);
  ull h2 = tree_hash(0, -1, adj2);
  cout << (h1 == h2 ? "YES" : "NO") << "\n";
}

# 트리 동형 판정, tuple 해시 memoization
import sys
input = sys.stdin.readline

adj1 = []
adj2 = []
memo = {}
next_id = [1]

def tree_hash(v, parent, adj):
  children = tuple(sorted(
      tree_hash(u, v, adj)
      for u in adj[v] if u != parent
  ))
  if not children:
      return 1
  if children in memo:
      return memo[children]
  memo[children] = next_id[0]
  next_id[0] += 1
  return memo[children]

n, m = map(int, input().split())
adj1 = [[] for _ in range(n)]
adj2 = [[] for _ in range(m)]
for _ in range(n - 1):
  u, v = map(int, input().split())
  u -= 1; v -= 1
  adj1[u].append(v)
  adj1[v].append(u)
for _ in range(m - 1):
  u, v = map(int, input().split())
  u -= 1; v -= 1
  adj2[u].append(v)
  adj2[v].append(u)
if n != m:
  print("NO")
else:
  h1 = tree_hash(0, -1, adj1)
  h2 = tree_hash(0, -1, adj2)
  print("YES" if h1 == h2 else "NO")

// 트리 동형 판정, HashMap 기반 메모이제이션
import java.util.*;
import java.io.*;

public class Main {
  static List<Integer>[] adj1, adj2;
  static Map<List<Long>, Long> memo = new HashMap<>();
  static long nextId = 1;

  static long treeHash(int v, int parent, List<Integer>[] adj) {
      List<Long> children = new ArrayList<>();
      for (int u : adj[v]) {
          if (u == parent) continue;
          children.add(treeHash(u, v, adj));
      }
      if (children.isEmpty()) return 1L;
      Collections.sort(children);
      if (memo.containsKey(children)) return memo.get(children);
      memo.put(new ArrayList<>(children), nextId);
      return nextId++;
  }

  public static void main(String[] args) throws IOException {
      BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
      StringTokenizer st = new StringTokenizer(br.readLine());
      int n = Integer.parseInt(st.nextToken());
      int m = Integer.parseInt(st.nextToken());
      adj1 = new ArrayList[n];
      adj2 = new ArrayList[m];
      for (int i = 0; i < n; i++) adj1[i] = new ArrayList<>();
      for (int i = 0; i < m; i++) adj2[i] = new ArrayList<>();
      for (int i = 0; i < n - 1; i++) {
          st = new StringTokenizer(br.readLine());
          int u = Integer.parseInt(st.nextToken()) - 1;
          int v = Integer.parseInt(st.nextToken()) - 1;
          adj1[u].add(v); adj1[v].add(u);
      }
      for (int i = 0; i < m - 1; i++) {
          st = new StringTokenizer(br.readLine());
          int u = Integer.parseInt(st.nextToken()) - 1;
          int v = Integer.parseInt(st.nextToken()) - 1;
          adj2[u].add(v); adj2[v].add(u);
      }
      if (n != m) {
          System.out.println("NO");
      } else {
          long h1 = treeHash(0, -1, adj1);
          long h2 = treeHash(0, -1, adj2);
          System.out.println(h1 == h2 ? "YES" : "NO");
      }
  }
}

stdin

결과

YES

복잡도

항목	값
시간 (최선)	O(N) - 자식 정렬 비용 무시 가능한 경우
시간 (평균)	O(N log N) - 각 노드의 자식 정렬
시간 (최악)	O(N log N)
공간	O(N) - DFS 스택 + 해시 테이블

정렬 없이 multiset hash 를 쓰면 O(N) 달성 가능 (소수 곱 hash). 실제 구현은 자식 수 작아서 O(N log N) 도 충분히 빠름.

변형 / 활용

1. Rooted vs Unrooted

rooted tree: 한 번의 DFS.
unrooted tree: 중심 (center) 또는 직경 중점을 루트로 삼아 두 번 시도.

2. 중복 서브트리 제거

서브트리 해시를 모아 frequency count. 같은 해시 여러 개 → 중복 구조.

3. 트리 변환 최소 비용

두 트리 diff 계산: 노드 해시 불일치 지점부터 edit distance.

함정

1. 해시 충돌

polynomial hash 는 확률적 충돌 (birthday paradox). N=10^5 수준에선 거의 없지만, critical 하면 두 해시 함수 병용.

2. 루트 선택 (unrooted)

unrooted tree 는 루트 위치에 따라 해시 달라짐. 중심 노드 (eccentricity 최소) 를 루트로 잡아야 canonical.

3. 자식 정렬 누락

자식 순서를 무시하려면 반드시 sort. 안 하면 순서만 바뀌어도 다른 해시.

4. 메모리 초기화

여러 테스트케이스가 있으면 memo 전역 map 을 매번 clear. 안 그러면 다른 트리 해시가 섞임.

BOJ 연습 문제

번호	제목	정답률	링크
BOJ 4788	중복 서브트리	-	kokoa-lab
BOJ 13306	트리	-	kokoa-lab
BOJ 15481	그래프와 MST	-	kokoa-lab

참고

이 글의 용어 (3개)

깊이 우선 탐색 (DFS)algorithm: 정의 깊이 우선 탐색 (Depth-First Search, DFS) 는 그래프 G=(V, E) 에서 갈 수 있는 만큼 깊이 들어가다가 막히면 백트래킹하는 알고리즘. 스택 (LIF…
문자열 해싱 (String Hashing)algorithm: 정의 문자열 해싱 (String Hashing) 은 문자열을 고정 길이의 정수 (해시값) 로 매핑하여, 부분 문자열 비교를 O(1) 에 수행할 수 있게 만드는 기법. Rabin과…
트리 (Trees)algorithm: 정의 트리 (Tree) 는 사이클이 없는 연결 그래프 (acyclic connected graph). N 개 정점이면 정확히 N-1 개 간선. 임의의 두 정점 사이에 유일한 경로…