[백준] 14725 - 개미굴

1. 문제

14725번: 개미굴

2. 개요

개미굴에 로봇 개미를 넣어 각 구역별로 저장된 먹이의 정보를 받아 개미굴의 구조를 구하는 문제.

3. 풀이 및 코드

3-1. 풀이

층마다 ‘—’ 로 구분하고 같은 층에 여러 먹이가 있다면 사전순으로 정렬한다.

처음엔 단순히 딕셔너리 하나로 구현해봤으나, 먹이 이름이 중복되면서 문제가 발생했다.

자식을 다시 딕셔너리로 만들어주면서 이를 부모로 재설정함으로 중복 문제를 해결할 수 있었다.

모든 먹이를 입력받아 다 넣고 난 후, 정렬하여 DFS로 탐색하면서 조건에 맞게 ‘—’를 붙여 출력한다.

3-2. Python

import sys

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

tunnel = dict()

for i in range(N):
    infos = list(sys.stdin.readline().split())

    parent = tunnel
    for j in range(1, 1 + int(infos[0])):
        if infos[j] not in parent:
            parent[infos[j]] = dict()

        parent = parent[infos[j]]

def DFS(d, idx = 0):
    for k in sorted(d.keys()):
        print("--" * idx + k)

        DFS(d[k], idx + 1)

DFS(tunnel)