백준 9328 열쇠

from collections import deque

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

t = int(input())

for _ in range(t):
    h, w = map(int, input().split())
    tmp_g = [list(input()) for _ in range(h)]
    keys = list(input())
    ans = 0
    g = [['.'] * w for _ in range(h)]

    for i in range(h):
        g[i] = ['.'] + tmp_g[i] + ['.']
    g = [['.'] * (w+2)] + g + [['.'] * (w+2)]

    def findkey(sx, sy):
        check = [[-1] * (w+2) for _ in range(h+2)]
        q = deque()
        q.append((sx, sy))
        check[sx][sy] = 0
        cnt = 0
        while q:
            x, y = q.popleft()
            for i in range(4):
                nx, ny = x + dx[i], y + dy[i]
                if nx < 0 or ny < 0 or nx >= h+2 or ny >= w+2:
                    continue
                if g[nx][ny] == '*':
                    continue
                if check[nx][ny] == -1:
                    if g[nx][ny].islower():
                        q.append((nx, ny))
                        check[nx][ny] = check[x][y] + 1
                        if g[nx][ny] not in keys:
                            keys.append(g[nx][ny])
                            cnt += 1
                    elif g[nx][ny].isupper():
                        if g[nx][ny].lower() in keys:
                            q.append((nx, ny))
                            check[nx][ny] = check[x][y] + 1
                    else:
                        q.append((nx, ny))
                        check[nx][ny] = check[x][y] + 1
        return cnt

    def bfs(sx, sy):
        global ans
        check = [[-1] * (w+2) for _ in range(h+2)]
        q = deque()
        q.append((sx, sy))
        check[sx][sy] = 0
        while q:
            x, y = q.popleft()
            for i in range(4):
                nx, ny = x + dx[i], y + dy[i]
                if nx < 0 or ny < 0 or nx >= h+2 or ny >= w+2:
                    continue
                if g[nx][ny] == '*':
                    continue
                if check[nx][ny] == -1:
                    if g[nx][ny] == '.' or g[nx][ny].islower():
                        q.append((nx, ny))
                        check[nx][ny] = check[x][y] + 1
                    elif g[nx][ny] == '$':
                        q.append((nx, ny))
                        check[nx][ny] = check[x][y] + 1
                        g[nx][ny] = '.'
                        ans += 1
                    else:
                        if g[nx][ny].lower() in keys:
                            q.append((nx, ny))
                            check[nx][ny] = check[x][y] + 1

    while True:
        cnt = findkey(0, 0)
        if cnt == 0:
            break

    bfs(0, 0)
    print(ans)

처음에는 check배열을 여러 차원으로 만들거나 정보를 여러개 저장할 생각으로 한번에 bfs를 돌려서 찾겠다고 생각했는데 쉽지 않았음

1. bfs로 찾을 수 있는 열쇠를 모두 찾는다
2. 열쇠를 찾은 후 문서를 모두 찾는다

빈칸으로 테두리 한번 패딩해줌 (들락날락할 수 있도록) -> 계속 bfs를 해주면서 key를 더이상 찾을 수 없을 때까지 key를 모두 찾아줌 -> bfs로 문서를 찾아줌