문제
풀이
Trie 구조에 대한 문제이다. 해당 값에 해당하는 노드가 없으면 만들고, 있다면 그곳을 따라가고 그 다음 노드를 향하게 하여 계속해서 반복하는 자료 구조이다.
후에 만들어진 자료 구조를 정렬하여 조건에 맞게 DFS로 정답을 도출해낸다.
Referece를 참조하였다.
소스 코드
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
import sys
from math import *
class trie:
def __init__(self):
self.root = {} #dictionary
def add(self, string):
current = self.root # 초기값 설정
for char in string:
if char not in current: #현재 노드에서 string의 해당 알파벳으로 시작되는게 없다면
current[char] = {} #dictionary #해당 알파벳 index로 dictionary 만든다
current = current[char] #만든 노드로 current 노드 변경
current[0] = True #모두 완료했다면 종료 표시
def travel(self, level, current):
if 0 in current: #문자열이 종료라면 Return
return
current_children = sorted(current) # 오름차순으로 문자열 정렬
for i in current_children:
print("--"*level + i)
self.travel(level+1, current[i]) #DFS
N = int(input())
nest = trie() #객체 선언
for _ in range(N):
input_line = sys.stdin.readline().split()
K = input_line[0]
foods = input_line[1:]
nest.add(foods)
nest.travel(0, nest.root)
