[백준 14725번] 개미굴 (Python3)

import sys
input = sys.stdin.readline

N = int(input())

child = {0:set()}
for _ in range(N):
  info = [*input().strip().split()]
  parent = 0
  for i in range(1,len(info)):
    child[parent].add((info[i],i-1,parent))
    parent = (info[i],i-1,parent)
    if child.get(parent):
      continue
    child[parent] = set()

for i in child:
  child[i] = sorted(child[i])

def DFS(now):
  name,depth,_ = now
  print("--"*depth,end="")
  print(name)
  for next in child[now]:
    DFS(next)

for now in child[0]:
  DFS(now)

 

엄청 쉬운 문제인줄 알았는데 조금 쉬웠던 문제.

그냥 단순하게 자식노드를 저장한 다음 DFS로 출력하면 된다고 생각했는데, 고려해야할 점이 몇가지 있었다.

 

일단 알고리즘을 요약하면

1. 데이터에 대해서 1층은 0의 자식으로 저장하고 나머지는 위층의 자식으로 저장

2. DFS로 전위순회 방식으로 출력

 

매우 간단하다.

그러나 고려해야할 점은

1. 같은 층에는 같은 이름이 없지만 다른 층에는 같은 이름이 있을 수 있다.

2. 같은 층이더라도 다른 부모를 가질 경우 같은 이름이 있을 수 있다.

라는 점이다.

 

따라서 부모와 자식의 이름을 그냥 입력주는대로 저장하는것이 아니라 튜플로 (이름, 층수, 부모) 로 저장해서 겹치지 않게 해주어야한다.

 

친절하게도 이 두 가지 반례를 테스트케이스 두개에 각각 넣어줘서 쉽게 디버깅할 수 있었다. 고마워요 출제자분!

 

조금 찾아보니 이 문제는 트라이 알고리즘을 입문하기 위한 문제라고 한다.

트라이 알고리즘에 대해서 한번 알아봐야겠다.

 

오늘의 교훈) 트라이 알고리즘에 대해서 알아보자