[백준] 14725 - 개미굴

문제 링크

https://www.acmicpc.net/problem/14725

문제 요약

이 문제는 로봇 개미들이 탐사한 개미굴의 구조를 기반으로, 개미굴의 층별 구조를 시각화하는 것입니다. 각 로봇 개미는 자신이 지나온 방에 있는 먹이 이름의 목록을 보내주며, 이 정보들을 종합하여 개미굴의 전체 구조를 계층적으로 표현해야 합니다. 중요한 점은:

• 각 층은 "--" 기호로 구분합니다.
• 같은 층에 여러 개의 방이 있을 경우, 사전 순서대로 출력해야 합니다.
• 최상위 굴에서 시작하여 개미굴의 전체 구조를 출력합니다.

푼 방법

이 문제를 해결하기 위해 트라이(Trie) 자료구조를 사용했습니다. 트라이는 문자열이나 시퀀스를 효율적으로 저장하고 검색하는 트리 형태의 자료구조입니다.

구현 단계는 다음과 같습니다:

1. 트라이 생성:
   • 각 노드는 먹이 이름을 키로 갖는 자식 노드들의 딕셔너리를 가집니다.
   • 루트 노드는 빈 노드로 시작합니다.
2. 입력 데이터 삽입:
   • 각 로봇 개미가 보내준 먹이 정보 리스트를 트라이에 삽입합니다.
   • 먹이 이름을 순서대로 따라가며, 노드가 없으면 새로운 노드를 생성하고, 있으면 해당 노드로 이동합니다.
3. 트라이 출력:
   • 트라이를 재귀적으로 탐색하면서 각 층의 먹이 이름을 출력합니다.
   • 자식 노드들은 사전 순서로 정렬하여 탐색합니다.
   • 출력 시, 층(level)에 따라 "--"를 반복하여 들여쓰기를 합니다.

정답 코드

import sys


class TrieNode:
    def __init__(self):
        self.children = {}

def insert(trie, foods):
    node = trie
    for food in foods:
        if food not in node.children:
            node.children[food] = TrieNode()
        node = node.children[food]

def dfs(node, level):
    for food in sorted(node.children.keys()):
        print("--" * level + food)
        dfs(node.children[food], level + 1)
        
n = int(sys.stdin.readline())
trie = TrieNode()

for _ in range(n):
    inputs = sys.stdin.readline().split()
    count = int(inputs[0])
    nodes = inputs[1:]
    insert(trie, nodes)

dfs(trie, 0)

배웠던 부분

트라이(Trie) 구조란?

트라이(Trie)는 "Retrieval"의 약어로, 문자열이나 시퀀스의 집합을 저장하고 효율적으로 검색하기 위한 트리 기반의 자료구조입니다.

• 구조:
  • 각 노드는 부분 문자열(또는 시퀀스의 요소)을 나타내며, 루트 노드는 공통된 접두사를 나타냅니다.
  • 경로를 따라 내려가면 전체 문자열 또는 시퀀스를 재구성할 수 있습니다.
• 특징:
  • 검색 효율성: 문자열의 길이에 비례하는 시간 복잡도로 검색이 가능하여, 많은 문자열을 저장하고 검색하는 데 효과적입니다.
  • 공간 효율성: 공통된 접두사를 공유하므로, 중복되는 부분을 효율적으로 저장할 수 있습니다.
• 사용 사례:
  • 사전(Dictionary) 구현
  • 자동 완성 기능
  • 접두사 검색
  • 문자열 통계 및 분석