백준 14725번: 개미굴 (Trie)

문제링크:14725번: 개미굴 (acmicpc.net)

14725번: 개미굴

문제 원리는 간단하게 DFS를 이용하여 각 간선들이 입력되면 이를 바탕으로 그래프를 만들어 문제에 주어진 대로 출력하는 것이지만 각 노드들이 문자열로 이루어져 있고, 중복되는 노드들이 있어서 문자열에 익숙하지 않아 어려웠다.

import sys

N=int(sys.stdin.readline().rstrip())

tree=dict()
for _ in range(N):
    inputs=list(sys.stdin.readline().rstrip().split())
    maxdepth=int(inputs[0])
    cur=tree
    for i in range(1,maxdepth+1):
        node=inputs[i]
        if node not in cur:
            cur[node]={}
        cur=cur[node]

def printtree(cur,depth):
    cur=dict(sorted(cur.items()))
    for child in cur.keys():
        print('--'*depth,child,sep='')
        printtree(cur[child],depth+1)
        
printtree(tree,0)

인터넷을 보니 파이썬의 딕셔너리 안에 딕셔너리를 넣는 것을 이용해 그래프를 구현하는 방법이 있었다. tree 딕셔너리의 깊이 1부터 탐색하여 만약 해당 문자열의 node가 있으면 그 node를 cur로 만들어 그 노드를 탐색하고, 없으면 그 깊이에 기존에 없던 새로운 노드라는 뜻이므로 새로 만들어 주고 그 노드를 탐색하며 진행한다.

 

printtree()함수는 dfs방식을 사용하여 현재 깊이의 노드를 일단 sort해주고, 맨 앞 노드를 출력하며 그 노드를 dfs 재귀를 사용하여 탐색 해 준다. 그렇게 하면 탐색하는 노드마다 sort가 될 것이다.

 

기존의 그래프 탐색 문제들은 보통 노드와 간선들이 숫자로 주어져 리스트와 그 인덱스를 이용해 그래프를 구현했지만, 문자열인 경우 어떻게 할 지 한번도 생각해 보지 못했었다. 다음엔 딕셔너리를 이용하면 될 것 같다. 몰랐는데 이렇게 문자열을 트리 형태로 만드는 것을 트라이 자료구조 라고 한다고 한다. 비슷한 문제를 더 풀어봐야 할 것 같다.