[BOJ] 14725 - 개미굴 (Python)

 

 

아이디어

 

트라이를 이용하여 공통되는 먹이 정보를 저장한 후 DFS로 먹이 정보를 출력한다.

 

 

풀이

 

클래스로 구현한 트라이 trie를 생성하여 insert로 단어들을 트라이에 넣고, search로 개미굴의 시각화된 구조를 출력한다.

 

트라이 객체 생성 시 루트 노드를 가리키는 root에 빈 딕셔너리를 할당한다.

insert 메서드는 먹이들이 루트 노드에서부터 차례로 자식 노드로 존재하지 않으면 자식 노드를 새로 생성한다.

search 메서드는 DFS로 정렬된 먹이 이름들에 차례로 깊이만큼 문자열 '--'을 더해 출력하는 함수 dfs를 호출한다.

 

import sys

input = sys.stdin.readline

class Trie:
    def __init__(self):
        self.root = dict()

    def insert(self, words):
        node = self.root
        for word in words:
            if word not in node:
                node[word] = dict()
            node = node[word]

    def search(self):
        def dfs(node, d):
            for c in sorted(node.keys()):
                print('--'*d+c)
                dfs(node[c], d+1)

        dfs(self.root, 0)

N = int(input())
trie = Trie()
for _ in range(N):
    K, *words = input().split()
    trie.insert(words)
trie.search()