[백준 9328번] 열쇠 (Python3)

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

def entrance():      #경계 주변을 돌면서 입구 좌표를 찾는 함수
  result = set()
  for i in range(N):
    if MAP[i][0] != "*":
      result.add((i,0))
    if MAP[i][M-1] != "*":
      result.add((i,M-1))
  for i in range(M):
    if MAP[0][i] != "*":
      result.add((0,i))
    if MAP[N-1][i] != "*":
      result.add((N-1,i))
  return result      #입구 좌표를 모은 set 반환

def BFS():
  global result
  visited = [[0]*M for i in range(N)]
  dq = deque(entranceset)    #입구좌표에서 BFS 시작

  while dq:
    y,x = dq.popleft()
    if visited[y][x]:
      continue
    visited[y][x] = 1
    if MAP[y][x] != ".":
      if MAP[y][x] == "$":    #문서 발견시 result +1
        result += 1
        MAP[y][x] = "."
      elif MAP[y][x].isupper():  #대문자일시 열쇠 있으면 .으로 바꾸기
        if not Key[MAP[y][x]]:
          continue
        MAP[y][x] = "."
      else:
        door = MAP[y][x].upper()
        MAP[y][x] = "."    #소문자일시 이미 있는 열쇠면 그대로 진행
        if not Key[door]:  #없는 열쇠면 열쇠 추가하고 BFS 처음부터 다시
          Key[door] = 1
          MAP[y][x] = "."
          BFS()
          return
    for i in range(4):
      y1,x1 = y+dy[i],x+dx[i]      #상하좌우 BFS
      if N>y1>=0 and M>x1>=0:
        if visited[y1][x1]:
          continue
        if MAP[y1][x1] == "*":
          continue
        dq.append((y1,x1))   

T = int(input())
for test in range(T):
  N,M = map(int,input().split())

  MAP = []
  for i in range(N):
    MAP.append(list(input().strip()))

  Key = {chr(i):0 for i in range(65,91)}  #모든 알파벳에 대한 열쇠 dict
  for i in input().strip():
    Key[i.upper()] = 1        #열쇠 있으면 1, 없으면 0
  entranceset = entrance()
  result = 0
  BFS()

  print(result)

 

쉬운 문제였지만 시간초과를 해결하려면 고려해야할 요소가 조금 있었던 문제이다.

BFS로 해결하였다.

 

기본적인 알고리즘은 

0. 모든 경계면에 대해서 입구좌표 찾아놓기

1. 모든 알파벳에 대해서 key dict 만들어서 열쇠 있는지 여부 확인

2. 열쇠가 있는 문이면 문 없애고, 없는 문이면 continue

3. 열쇠 발견시 이미 있는 열쇠면 열쇠 없애고 그대로 진행, 없는 열쇠면 처음부터 다시 BFS

4. 결과출력

 

 

이때 시간초과가 났던 이유는 3번 때문이었다.

아마 테스트케이스 중에서 똑같은 열쇠를 수천개 넣어놓은 케이스가 있는 모양이다.

재귀에러가 났을때부터 알아봤어야 했는데, 재귀에러를 sys.setrecursion으로 해결하려 하니 시간초과가 났다.

 

 

오늘의 교훈) 불필요한 동선을 줄이자