열쇠

입력

3
5 17
*****************
.............**$*
*B*A*P*C**X*Y*.X.
*y*x*a*p**$*$**$*
*****************
cz
5 11
*.*********
*...*...*x*
*X*.*.*.*.*
*$*...*...*
***********
0
7 7
*ABCDE*
X.....F
W.$$$.G
V.$$$.H
U.$$$.J
T.....K
*SQPML*
irony

출력

3
1
0

코드

참고

from collections import deque
import sys

input = sys.stdin.readline

dx = [0, 0, 1, -1]
dy = [1, -1, 0, 0]


def bfs(x, y):
    visited = [[0 for _ in range(w + 2)] for _ in range(h + 2)]
    q = deque([[x, y]])
    visited[x][y] = 1
    count = 0
    while q:
        x, y = q.popleft()

        for i in range(4):
            xx = x + dx[i]
            yy = y + dy[i]
            if 0 <= xx < h + 2 and 0 <= yy < w + 2:
                if visited[xx][yy] == 0:
                    what = graph[xx][yy]
                    if what == ".":
                        visited[xx][yy] = 1
                        q.append([xx, yy])
                    elif what.islower():  # key
                        doors[ord(what) - ord('a')] = 1
                        graph[xx][yy] = "."
                        # 큐와 방문 리스트 초기화 -> key를 새롭게 추가했으니까 (큐와 방문 리스트 초기화 or 비트마스킹)
                        # 열지 못했던 door들을 다시 찾아 갈 수 있도록 visited 배열도 초기화 해준다. (ㅁㅊ)
                        q = deque([[xx, yy]])
                        visited = [[0 for _ in range(w + 2)] for _ in range(h + 2)]
                    elif what.isupper():  # door
                        if doors[ord(what) - ord('A')] == 1:
                            visited[xx][yy] = 1
                            q.append([xx, yy])
                    elif what == "$":
                        count += 1
                        graph[xx][yy] = "."
                        q.append([xx, yy])
    return count


for _ in range(int(input())):
    h, w = map(int, input().split())
    doors = [0 for _ in range(26)]

    # 그래프 외곽에 .을 추가하면 시작점을 찾을 필요 없다.
    # 별다른 처리 없이 빌딩 안팍을 드나들 수 있다. (👍)
    graph = [["." for _ in range(w + 2)]]
    graph.extend([["."] + list(input().rstrip()) + ["."] for _ in range(h)])
    graph.append(["." for _ in range(w + 2)])
    key = input().strip()

    if key != "0":
        for k in key:
            doors[ord(k) - ord('a')] = 1

    # 기존의 그래프에서 열 수 있는 door를 연다.
    for i in range(1, h + 1):
        for j in range(1, w + 1):
            if ord('A') <= ord(graph[i][j]) <= ord('Z'):
                if doors[ord(graph[i][j]) - ord('A')] == 1:
                    graph[i][j] = "."

    print(bfs(0, 0))

충격적인 발견

elif what.islower():  # key
    doors[ord(what) - ord('a')] = 1
    graph[xx][yy] = "."
    # 큐와 방문 리스트 초기화 -> key를 새롭게 추가했으니까 (큐와 방문 리스트 초기화 or 비트마스킹)
    # 열지 못했던 door들을 다시 찾아 갈 수 있도록 visited 배열도 초기화 해준다. (ㅁㅊ)
    q = deque([[xx, yy]])
    visited = [[0 for _ in range(w + 2)] for _ in range(h + 2)]

새로운 key를 얻었을 때 비트 마스킹으로 상황을 구분할 수 있지만, 큐와 visited 배열을 초기화하여 구분할 수 도 있다.

# 그래프 외곽에 .을 추가하면 시작점을 찾을 필요 없다.
# 별다른 처리 없이 빌딩 안팍을 드나들 수 있다. (👍)
graph = [["." for _ in range(w + 2)]]
graph.extend([["."] + list(input().rstrip()) + ["."] for _ in range(h)])
graph.append(["." for _ in range(w + 2)])
key = input().strip()

조건이 까다롭다면 생각의 전환이 필요하다