14725번: 개미굴

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

 

# https://www.acmicpc.net/problem/14725
# Tree, DFS

import sys
from collections import defaultdict

sys.setrecursionlimit(10**8)

N = int(input())

tree = defaultdict(list)
start = set([])
for _ in range(N) :
    path = sys.stdin.readline().split()
    num_rooms = int(path[0])
    rooms = path[1:]

    path_name = ''
    for idx in range(num_rooms) :
        if idx == 0 :
            path_name = rooms[idx]
            start.add(path_name)
        else :
            new_path_name = path_name + '/' + rooms[idx]
            tree[(path_name)].append((new_path_name))
            path_name = new_path_name

visited = defaultdict(int)

def DFS(node) :
    if visited[node] != 0 :
        return

    visited[node] = 1
    nodes = node.split('/')
    now_node = nodes[-1]
    print('--' * (len(nodes)-1) + now_node)
    for l in sorted(tree[node]) :
        if visited[l] == 1 :
            continue

        DFS(l)

for s in sorted(start) :
    DFS(s)

 

같은 이름을 가진 노드가 있을 수 있어 path 이름으로 tree를 생성했다.

예를 들어, 

위와 같은 입력이 주어졌을 때, defaultdict에

tree['B'], tree['B/A']

tree['A'], tree['A/B'], tree['A/B/C'] ...

이런 방식으로 입력하여 트리를 생성한다.

 

이후 DFS를 수행하면서, 방문한 노드의 '/'의 갯수만큼 '--'를 출력하고 방문한 노드를 출력한다.