[Baekjoon] 개미굴(python)

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

문제 접근

트리를 생성하면 풀 수 있는 문제이다.

 

트리를 만들 때 딕셔너리나 리스트를 이용해서 만들 수 있는데 이 문제는 노드의 값이 정수형이 아닌 문자열이므로 Dictionary를 이용하여 트리를 생성하도록 한다.

---

풀이 과정

1. 트리를 생성한다.

주어진 입력에서 depth별 노드의 정보를 받을 수 있다.

재귀를 통해 입력받은 리스트를 하나씩 트리에 추가한다.

def add_tree(tree, nodes):
    if not nodes:
        return

    if nodes[0] not in tree:
        tree[nodes[0]] = {}

    add_tree(tree[nodes[0]], nodes[1:])

 

2. 트리를 출력한다.

트리를 출력할 때 DFS를 통해 트리를 탐색하면서 노드를 출력하면 된다.

 

각 Depth별로 사전 순서가 앞서는 노드부터 출력해야 하므로, 자식 노드들을 Sorting해서 탐색하도록한다.

def print_tree(tree, depth):
    for node in sorted(tree.keys()):
        print("--" * depth + node)

        print_tree(tree[node], depth + 1)

---

정답 코드

"""
    백준 14725번 개미굴
"""

import sys


def add_tree(tree, nodes):
    if not nodes:
        return

    if nodes[0] not in tree:
        tree[nodes[0]] = {}

    add_tree(tree[nodes[0]], nodes[1:])


def print_tree(tree, depth):
    for node in sorted(tree.keys()):
        print("--" * depth + node)

        print_tree(tree[node], depth + 1)


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

trees = {}

for _ in range(N):

    info = list(sys.stdin.readline().split())

    nodes = info[1:]

    add_tree(trees, nodes)

print_tree(trees, 0)