접근 과정
오 열쇠? 비트마스킹이네 달이 차오른다 가자 문제랑 비슷해 보이는데
# 말도 안되는 생각을 해보았다..
visited = [[[0]*(1<<26) for _ in range(100)] for _ in range(100)]키 개수가 최대 26개니까,, 1<<26이면.. 6천만개네..
배열 돌려볼까? 음 역시 메모리 초과나네..
아 A 출입구로 가서 키를 먹고 나면 B 출입구로 들어 갔을때 막혔던 부분은 열 수 있네..
이러면 출입구만 따로 관리한다고 될 일이 아닌데?
테두리를 전부 . 처리해서 이동할 수 있는 공간으로 만들자
키를 먹으면 주인공이 그 위치에 가서 없애는 방식이 아니라 애초에 입력 받을 때 문 좌표를 입력받고
해당 키를 먹으면 그 문을 . 처리 해버리자!
문제 설명
- 문서 '$'를 몇 개나 획득할 수 있는지를 출력하는 문제다.
- 열쇠(소문자) 하나로 문(대문자) 여러개를 열 수 있다.
- 달이 차오른다 가자 문제와 매우 비슷하지만 푸는 방법은 다르다.
풀이 설명
-
테두리를 '.'으로 한 줄씩 둘러준다.
-
벽면과 맞닿아 있는 '.'으로 자유롭게 출입이 가능하다는 말은 외곽으로 이동이 가능하다는 뜻이다.
-
- 열쇠를 미리 소지하고 있거나, 돌아 다니다가 열쇠를 획득하면 그 즉시 해당되는 문을 개방시킨다.
-
openDoor(key) 함수를 이용해 키를 전달하면 해당되는 모든 문을 열어줬다.
-
- 열쇠를 획득하고 문을 개방했다면 visited를 초기화 해줘서 다시 돌아다닐 수 있게 해준다.
-
물론 문에서 막힌 부분만 따로 저장해 뒀다가 해당 문이 열리면 그 부분부터 시작해줘도 된다.
-
소스 코드
##########################################################
import sys
from collections import deque
direction = [[0,1],[-1,0],[1,0],[0,-1]] #for BFS
input = sys.stdin.readline
def ip():return input().rstrip()
def lip():return list(ip())
def ips():return ip().split()
def ii():return int(input())
def mii():return map(int,ips())
def lmii():return list(mii())
##########################################################
for _ in range(ii()):
h,w = mii()
alpha_door = 'ABCDEFGHIJKLMNOPQRSTUVWXYZ'
alpha_key = 'abcdefghijklmnopqrstuvwxyz'
docuCnt = 0
field = list()
field.append(list('.'*(w+2)))#윗면 채우기
doorPosition = [[] for _ in range(26)]#문의 최대 수만큼
for i in range(h):
tmp = lip()
for j in range(w):#문의 위치를 알파벳별로 미리 파악해둔다.
if tmp[j] in alpha_door:
doorPosition[ord(tmp[j])-65].append([j+1,i+1])
elif tmp[j]=='$':#문서의 수를 미리 세두고 다 찾으면 빨리 끝내자.
docuCnt+=1
field.append(list('.')+tmp+list('.'))
field.append(list('.'*(w+2)))#아랫면 채우기
def openDoor(key):#키를 전달하면 해당되는 모든 문을 열어주는 함수
for dopX,dopY in doorPosition[ord(key)-97]:
field[dopY][dopX]='.'
keyarr = lip() #소유한 키의 상태를 저장한다.
if keyarr[0]=='0':
keyarr=list()#소유한 키가 없는 경우는 넘어간다.
else:
for k in keyarr:
openDoor(k)#이미 획득한 키는 문을 미리 열어둔다.
answer =0
def bfs():
global answer
visited = [[0]*(w+2) for _ in range(h+2)]
visited[0][0]=1
q = deque([[0,0]])
while q:
x,y = q.popleft()
for dx,dy in direction:
nx,ny = x+dx,y+dy
if 0<=nx<w+2 and 0<=ny<h+2 and visited[ny][nx]==0:
fyx = field[ny][nx]
if fyx=='.':
visited[ny][nx]=1
q.append([nx,ny])
elif fyx=='$':
answer+=1
if docuCnt==answer:
return
field[ny][nx]='.'
visited[ny][nx]=1
q.append([nx,ny])
elif fyx in alpha_key:#키를 만나면
field[ny][nx]='.'
q.append([nx,ny])
if fyx not in keyarr:
keyarr.append(fyx)
openDoor(fyx)#해당되는 문열고
#visited 리셋
visited = [[0]*(w+2) for _ in range(h+2)]
visited[ny][nx]=1
q.append([nx,ny])
bfs()
print(answer)