[백준 9202번] Boggle (Python3)

import sys
input = sys.stdin.readline
dy = [1,1,1,0,-1,-1,-1,0]; dx = [1,-1,0,1,1,-1,0,-1]
score = [0,0,0,1,1,2,3,5,11]

def update(word):
  now = Dict
  for w in word:
    if not now.get(w):
      now[w] = {}
    now = now[w]
  now[0] = 1

def find(y,x,bit,now,word):
  if now.get(0):
    words.add(word)
  for i in range(8):
    y1,x1 = y+dy[i],x+dx[i]
    if 4>y1>=0 and 4>x1>=0:
      if bit&(1<<y1*4+x1):
        continue
      w = board[y1][x1]
      if now.get(w):
        find(y1,x1,bit|(1<<y1*4+x1),now[w],word+w)

Dict = {}
for _ in range(int(input())):
  update(input().strip())
input()
for _ in range(int(input())):
  board = [input().strip() for i in range(4)]
  words = set()
  for y in range(4):
    for x in range(4):
      if Dict.get(board[y][x]):
        find(y,x,1<<y*4+x,Dict[board[y][x]],board[y][x])
  print(sum([score[len(i)] for i in words]),sorted([(-len(i),i) for i in words])[0][1],len(words))
  input()

Dict를 이용한 트라이로 해결하였다.

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

 

일단 풀이부터 설명하면,

1. 모든 단어에 대해서 trie를 만든다.

2. DFS로 board를 8방향 탐색하여 단어를 찾는다.

3. 결과를 출력한다.

 

아주 간단한 문제인데, 문제를 잘못 해석해서 시간을 어마어마하게 날렸다.

"한 주사위는 단어에 한 번만 사용할 수 있다" 라는 말을 전체 점수의 총합을 구할 때 주사위를 한번만 써야하는 것인줄 알고, 비트마스킹+DFS로 최댓값을 구하려고 노력했는데, 알고보니 그냥 단어만 찾고 점수 총합내면 되는 문제였다...

 

난이도기여 내역을 보니

나와 비슷한 실수를 한 사람들도 꽤 있는걸로 보아 지문이 좀 더 명확해야 하지 않나 하는 아쉬움이 남는다.

 

 

오늘의 교훈) 문제를 정확하게 이해하자