[백준 5446번] 용량 부족 (Python3)

import sys
input = sys.stdin.readline

def update(word,n):
  now = Dict
  for w in word+"#":
    now[n] = 1
    if not now.get(w):
      now[w] = {}
    now = now[w]
  now[n] = 1

def DFS(now):
  global result
  if not now.get(1):
    return
  if not now.get(0) or len(now)==2:
    result += 1
    return
  for w in now:
    if w==0 or w==1:
      continue
    DFS(now[w])

for _ in range(int(input())):
  Dict = {}  
  for _ in range(int(input())):
    update(input().strip(),1)
  for _ in range(int(input())):
    update(input().strip(),0)
  
  result = 0
  DFS(Dict)
  print(result)

트라이 응용문제이다.

휴대폰 자판 [백준 5670번] 휴대폰 자판 (Python3) (tistory.com) 문제와 유사하다.

 

풀이를 설명하면,

1. Dict 자료구조를 이용해서 트라이를 만든다. 이때, 삭제해야하는 문자의 모든 dict에는 1을, 남겨두어야하는 문자의 모든 dict에는 0을 넣는다.

2. 편의를 위해 단어의 가장 마지막에는 쓰이지 않는 문자를 삽입한다. (나는 "#"을 삽입했다)

3. DFS로 탐색한다.

4. 탐색하면서 현재 위치의 key에 1이 존재하지 않으면 return한다. (삭제할 필요 없음)

5. 탐색하면서 현재 위치에 1이 존재하고, 0이 존재하지 않으면 삭제횟수를 +1 하고 return한다. (남겨두어야할 문자가 없으므로 모두 삭제하면 됨)

6. 탐색하면서 현재 위치에 1과 0이 모두 존재하면 다음 자식노드를 탐색한다.

7. 최종 삭제횟수를 출력한다.

 

 

오늘의 교훈) 트라이 알고리즘은 유용하다.