PS Featured

[PS] BOJ 14725 / 개미굴

Minjun Kim

07 Dec 2025 • 3 min read

Thumbnail: Photo by Salmen Bejaoui (Unsplash)

문제 링크: https://www.acmicpc.net/problem/14725

트라이(Trie)의 개념을 이해하기에 좋은 문제입니다.

풀이

Trie?

Trie란, 문자열을 저장하고 효율적으로 탐색하기 위한 트리 형태의 자료구조입니다.
문자열 자동 완성, 사전 검색 등의 기능을 구현하는데 자주 사용됩니다.
Radix Tree, Prefix Tree, Retrieval Tree라고도 부릅니다.

문자열 탐색이 빠릅니다.
전체 문자열을 하나하나 비교하면서 탐색하기보다, 문자열을 작은 단위로 쪼개어 그 조합을 찾는 방식으로, 시간 복잡도 면에서 유리합니다.
각 노드에서 자식 노드의 정보를 포인터 배열로 모두 저장하고 있어, 공간 복잡도가 큰 편입니다.

Trie에 데이터 저장하기

각각의 개미가 방문하는 각각의 방을 노드로 저장해 Trie에 연결해주면 됩니다.

최상위 굴을 포함하여 하나의 굴에서 개미굴이 여러 개로 나뉠 때 먹이 종류별로 최대 한 번만 나올 수 있다고 조건이 명시되어 있습니다. Trie의 구조 또한 같은 깊이에 같은 부모와 키를 가지는 노드는 하나만 존재하게 구성되므로, Trie를 활용하기에 유리합니다.

class Node:
    """Trie의 노드 클래스."""
    def __init__(self, key, value):
        self.value = value
        self.children = {}
    
    def add_child(self, value):
        """
        value를 값으로 가지는 새 자식 노드를 만든다. 
        만약 기존에 같은 값을 가지는 자식 노드가 존재한다면, 
        새로 만드는 대신 기존 노드를 반환한다.
        """
        try:
            return self.children[value]
        except KeyError:
            self.children[value] = Node(value)
            return self.children[value]
    
    def get_child(self, value):
        return self.children.get(value)
    
root = Node(None)

for _ in range(int(input())):
    line = input().rstrip().split()
    K = int(line[0])

    # Trie 구성하기
    cur = root
    for word in line[1:]:
        cur = cur.add_child(word)

Trie에 입력 데이터 저장하기

Trie 구조 조회하기

이제 구성한 Trie의 정보를 토대로 개미굴의 구조를 출력해야 합니다.

재귀 함수를 통해, 사전 순으로 각 자식 노드들을 깊이 우선으로 탐색하며 출력해주면 됩니다.

# Trie 구조를 출력하는 함수
def print_node(node, depth=0):
    print(f"{'--'*depth}{node.value}")
    
    for child in sorted(node.children.keys()):
        print_node(node.children[child], depth + 1)

def print_trie(root):
    for child in sorted(root.children.keys()):
        print_node(root.children[child], 0)
    
root = Node(None)

# 입력 데이터로 Trie 구성하기...

# Trie 구조 출력하기
print_trie(root)

Trie 구조 출력하기

전체 코드

class Node:
    """Trie의 노드 클래스."""
    def __init__(self, value):
        self.value = value
        self.children = {}
    
    def add_child(self, value):
        try:
            return self.children[value]
        except KeyError:
            self.children[value] = Node(value)
            return self.children[value]
    
    def get_child(self, value):
        return self.children.get(value)

# Trie 구조를 출력하는 함수
def print_node(node, depth=0):
    print(f"{'--'*depth}{node.value}")
    
    for child in sorted(node.children.keys()):
        print_node(node.children[child], depth + 1)

def print_trie(root):
    for child in sorted(root.children.keys()):
        print_node(root.children[child], 0)
    
root = Node(None)

input = open(0).readline

for _ in range(int(input())):
    line = input().rstrip().split()
    K = int(line[0])

    # Trie 구성하기
    cur = root
    for word in line[1:]:
        cur = cur.add_child(word)

# Trie 구조 출력하기
print_trie(root)

solution.py