[BOJ/백준] 14725 개미굴

import sys


class Node():
    def __init__(self,key=None,data=None):
        self.key = key
        self.data = data
        self.depth = 0
        self.child_node = {}
class Trie():
    def __init__(self):
        self.rootnode = Node()
    
    def insert(self,arr):
        cur_node = self.rootnode

        for node in arr:
            if node not in cur_node.child_node.keys():
                cur_node.child_node[node] = Node(node)
            cur_node.child_node[node].depth = cur_node.depth+1
            cur_node = cur_node.child_node[node]
        cur_node.data = 'END'
    def print(self):
        cur_node = self.rootnode
        stack = sorted(cur_node.child_node.values(),key= lambda x : (x.key),reverse=True)
        result = ''
        while stack:
            node = stack.pop()

            current_depth = node.depth
            result = '--'*(current_depth-1)+node.key
            print(result)
            if node.data == None:
                child_node = sorted(node.child_node.values(),key= lambda x : (x.key),reverse=True)
                stack.extend(child_node)

input = sys.stdin.readline
N = int(input())
trie = Trie()
for _ in range(N):
    N,*arr = input().split()
    N = int(N)
    trie.insert(arr)

trie.print()

트라이 알고리즘 문제를  처음 풀어본 유형이었다.

 

그래서 풀기 어려웠고, trie를 공부한 뒤에 풀 수 있었다.

 

이 문제는 전형적인 트라이 알고리즘으로, 현재 노드의 자식노드들을 저장하고,

 

자식노드에 해당 값이 있으면, 넘어가고, 없는 새로운 값이면 child_node에 Node를 추가시켜주면 된다.

 

그리고 print 또한 반복문적으로 끝까지 반복해서 들어가면 된다.

 

그런 방식으로 풀어주면 되는 문제였고, 좀 더 간단하게 풀어주기 위해, 해당 depth를 저장시켜주었다.