[BOJ] 백준 14725번 문제 풀이 (Python)

1. 문제 풀이

문자열을 이용해 트리를 만드는 것이 쉽지 않았다. 입력된 경로를 통해 중복으로 자식 노드를 만들지 않기 위해서 dictionary를 이용해야했는데 여러 겹으로 중첩된 dictionary를 만드는 것을 지금까지 문제를 풀면서 시도해본 적이 많이 없기 때문에 어려웠다.

문자열을 이용한 트리 구조를 찾아보았고 Trie 자료구조가 있다는 것을 알게되었다.

트라이(Trie)

문자열을 저장하고 효율적으로 탐색하기 위한 트리 자료구조. 자동완성, 사전에서 찾기, 문자열 검사에 사용된다.

1. 트리에 쓰이는 Node 구현
   • key: 해당 Node가 가진 문자(character)
   • children: key 이후 나오는 다음 문자
2. 정의한 Node를 이용해 Trie class 구현
   • head: 트리의 root 역할
   • insert(string) 메소드: string의 문자들을 하나씩 읽으면서 트리를 만든다.

2. 코드

import sys
def input(): return sys.stdin.readline().rstrip()

class Node:
    def __init__(self, key):
        self.key = key
        self.children = {}

class Trie:
    def __init__(self):
        self.head = Node(None)
    def insert(self, string):
        curr_node = self.head
        for c in string:
            if c not in curr_node.children:
                curr_node.children[c] = Node(c)
            curr_node = curr_node.children[c]

def print_node(now:Node, i:int, isHead=False):
    '''
    문제에서 요구하는 형식으로 출력하는 함수
    '''
    if not isHead:
        print("--"*i + now.key)
    sorted_keys = sorted(now.children.keys())
    for child in sorted_keys:
        print_node(now.children[child], i+1)

n = int(input())
trie = Trie()
for _ in range(n):
    path = input().split()[1:]
    trie.insert(path)
print_node(trie.head,-1,True)