문제 : https://www.acmicpc.net/problem/9328

문제

1층짜리 빌딩의 높이와 너비가 주어진다(필자는 잘못봐서 board의 가장 밑부분이 1층인지 앎).
1층의 건물도가 다음줄에 주어짐.

• : 벽
  . : 빈 곳
  $ : 문서
  소문자 알파벳 : 키
  대문자 알파벳 : 문

이제 주어진 board판에 대해서 주인공이 최대 몇개의 문서있는곳을 방문할 수 있는지 체크하면 된다.

풀이

키가 주어졌다고 저번처럼 비트마스킹 했다가 배열을 만드는 과정에서 매우 오래걸림. 따라서 딕셔너리를 이용하여 key들을 저장하고 bfs방식으로 탐색하면 된다. 이때 문을 방문하는 것이 까다로울 수 있다. 문을 방문했을 때 해당 열쇠가 있다면 바로 큐에 저장시키면 되지만 없다면??
필자는 딕셔너리를 하나 더 만들어서 해당 문에 대한 좌표들을 저장했다. 따라서 문에 방문했을 때 열쇠가 없다면 위 딕셔너리에 저장시키고, 해당 열쇠를 방문하면 그때의 딕셔너리 키 값을 열쇠로 하여 좌표들을 모두 q에 넣어주었다. 이렇게 해도 되는 이유는 q를 돌면서 방문할때 문이 있어 방문 못한곳들만 탐색해주기 위해서이다.
또한 문제를 자세히 보면 바깥 어디든 벽만 아니면 들어갈 수 있다고 하였으므로 board의 가장자리를 '.'로 넓혀주면 보다 간단히 코드를 작성할 수 있다.

code

from collections import deque

T = int(input())

def bfs(board,h,w,keys):
    answer = 0
    q=deque()
    q.append((0,0))
    visit = [[False]*w for _ in range(h)]
    visit[0][0]=True
    no_enter = {chr(ord('a')+i):[] for i in range(26)}
    dy = [0,0,-1,1]
    dx = [-1,1,0,0]
    
    while q:
        y,x = q.popleft()
        if board[y][x] =='$':
            answer += 1
        for i in range(4):
            ny = y+dy[i]
            nx = x+dx[i]
            if not (0<=ny<h and 0<=nx<w):
                continue
            if visit[ny][nx]:
                continue
            visit[ny][nx] = True
            ch = board[ny][nx]
            if ch=='*':
                continue
            if 'a'<=ch<='z':
                keys[ch]=True
                q.append((ny,nx))
                for _y, _x in no_enter[ch]:
                    q.append((_y,_x))
                no_enter[ch].clear()
            elif 'A'<=ch<='Z':
                ch = ch.lower()
                if keys[ch]:
                    q.append((ny,nx))
                else:
                    no_enter[ch].append((ny,nx))
            else:
                q.append((ny,nx))
    return answer

for _ in range(T):
    h,w = map(int,input().split())
    h+=2
    w+=2
    board = []
    for i in range(h):
        if i==0 or i==h-1:
            board.append(['.']*w)
            continue
        board.append(list(input()))
        board[i] = ['.'] + board[i] + ['.'] # 칸 늘려주기
    
    keys = {chr(ord('a')+i):False for i in range(26)}
    
    pre_keys = input()
    if pre_keys == '0':
        pre_keys = ''
    for i in pre_keys:
        keys[i]=True
    print(bfs(board,h,w,keys))
    

result

문제조건이 까다롭다 보니 error가 많이 발생했는데 코드를 짤 때 급하게 짜는 버릇좀 고쳐야겠다.