[백준] 개미굴

https://www.acmicpc.net/problem/14725

14725번: 개미굴

간단한 트라이 문제입니다. dict를 활용하여 연결되는 개미굴을 이동할 때마다 dict도 같이 이동하면서 없는 경우에는 dict를 생성해주면 된다. 출력을 할때에는 dict의 key들이 먹이들이 되므로 key들을 정렬하여 dfs로 탐색하면서 출력해주면 됩니다.

 

import sys, heapq
from collections import deque, defaultdict

sys.setrecursionlimit(10 ** 8)
INT_MAX = sys.maxsize
sys.stdin = open("input.txt", "r")
input = sys.stdin.readline

graph = {}

n = int(input())

for _ in range(n):
    data = list(input().split())

    cnt = int(data[0])

    cur = graph

    for i in range(cnt):
        food = data[1 + i]
        if food not in cur:
            cur[food] = {}
        cur = cur[food]

def dfs(cur_graph, cnt):
    keys = cur_graph.keys()

    for key in sorted(keys):
        for i in range(cnt):
            print("--", end="")
        print(key)
        dfs(cur_graph[key], cnt + 1)

dfs(graph, 0)