[백준 1194번] 달이 차오른다, 가자. (Python3)

풀이법은 금방 생각이 났는데, 내가 기피하는 방식이 여럿 사용되어서 풀기 까다로웠던 문제다.

 

일단 이 문제는 비트마스킹 문제이다. 비트마스킹을 이용해서 현재 가지고 있는 Key를 저장해놓는 방식으로 풀 수 있다. 또, 3차원 visited 리스트를 이용해서 풀어야 한다.

 

하지만 나는 평소에 3차원 visited 리스트도 사용하기 꺼려하고 (보통 마킹하는 숫자를 바꾸는걸 선호), 비트마스킹은 공부하려다가 다음에 해야지 하고 미뤄뒀었다.

그러다 보니까 시간초과, 메모리초과, 틀렸습니다 아주 각양각색으로 제출을 실패한 끝에 겨우 성공하였다.

 

import sys
input = sys.stdin.readline
from collections import deque
dy = [1,-1,0,0]
dx = [0,0,1,-1]

N,M = map(int,input().split())

board = []
for i in range(N):
  board.append([*input().strip()])

for i in range(N):
  for j in range(M):
    if board[i][j] == "0":
      minsik = (i,j)
      board[i][j] = "."

def BFS():
  dq = deque()
  dq.append((*minsik,0,""))
  visited = {"":[[0]*M for i in range(N)]}

  while dq:
    y,x,cnt,Key = dq.popleft()
    if visited[Key][y][x]:
      continue
    visited[Key][y][x] = 1
    yx = board[y][x]
    if yx == "1":
      return cnt
    if yx != ".":
      if yx.isupper():
        if yx.lower() not in Key:
          continue
      else:
        if yx not in Key:
          Key = "".join(sorted([*(Key+yx)]))
          visited[Key] = [[0]*M for i in range(N)]
          visited[Key][y][x] = 1
    for i in range(4):
      y1,x1 = y+dy[i],x+dx[i]
      if N>y1>=0 and M>x1>=0:
        if visited[Key][y1][x1] or board[y1][x1] == "#":
          continue
        dq.append((y1,x1,cnt+1,Key))
  return -1

print(BFS())

 

알고리즘을 요약하면 이러하다.

1. x,y값과 cnt(이동거리), 가지고 있는 Key를 deque에 저장한다.

2. BFS로 4방향을 탐사

3. 대문자 발견시 Key를 가지고 있으면 그대로 진행, 없으면 continue

4. 소문자 발견시 이미 있는 열쇠면 그대로 진행, 없는 열쇠면 Key 문자열에 추가, 이때 문자열을 sort한다.

5. visited는 가지고 있는 Key에 따라 dict로 불러온다.

 

Key 문자열을 비트마스킹으로 구현했다면 훨씬 빠르고 간단했겠지만, 일단 비스무리하게라고 풀기 위해서 어쩔수 없이 문자열로 구현하였다. (리스트나 dict의 경우 모든 리스트가 같이 변한다)

 

 

오늘의 교훈) 비트마스킹에 대해서 공부하고 3차원 리스트를 이용하자.