백준 14725번: 개미굴 (Python)

접근

처음에는 트라이가 무엇인지 모르고 풀었고, 이후에 트라이에 대해 공부하고 다른 분의 코드도 참고하여 트라이를 이용하여 풀었다.

첫번째 풀이는 모든 리스트를 저장 및 sort 한 후, 이전 문자열과 동일한 문자가 몇번 나오는지 체크하여 중복되지 않는 부분부터 결과를 출력하도록 코딩하였다.

트라이를 이용한 방법은 Node 에 자식 노드들을 저장하여 점점 내려가면서 자식들을 순서대로 표시하는 방법이다.

코드1

트라이를 사용하지 않은 코드

import sys

n = int(sys.stdin.readline())
array = []
for _ in range(n):
    tmp = list(sys.stdin.readline().split())
    array.append(tmp[1:])
array.sort()

for j in range(len(array[0])):
    print("--" * j + array[0][j])
for i in range(1, n):
    count = -1
    for j in range(len(array[i])):
        if len(array[i - 1]) <= j or array[i - 1][j] != array[i][j]:
            break
        else:
            count = j
    for j in range(count + 1, len(array[i])):
        print("--" * j + array[i][j])

코드2

트라이를 사용한 코드

import sys


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


class Trie():
    def __init__(self):
        self.head = Node(None)

    def insert(self, string):
        curr_node = self.head
        for char in string:
            if char not in curr_node.children:
                curr_node.children[char] = Node(char)
            curr_node = curr_node.children[char]

    def print_trie(self, L, curr_node):
        if L == 0:
            curr_node = self.head
        for child in sorted(curr_node.children.keys()):
            print("--" * L, child, sep="")
            self.print_trie(L + 1, curr_node.children[child])


trie = Trie()
n = int(sys.stdin.readline())
for _ in range(n):
    temp = list(sys.stdin.readline().split())
    trie.insert(temp[1:])
trie.print_trie(0, None)

더 생각해 볼 것?

...

코드나 내용 관련 조언, 부족한 점 및 질문 언제든 환영합니다!