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으로 해결하려 하니 시간초과가 났다.
오늘의 교훈) 불필요한 동선을 줄이자