[백준] 9328번 : 열쇠 풀이(python)

✅문제

출처 : 백

✅문제 풀이 

BFS를 큐 27개로 수행

- 큐 1개 : 일반적인 BFS

- 큐 26개 : 알파벳 문을 위한 큐

 

1. 테두리에 "." 추가후 BFS 실행

2. 대문자 알파벳 문에 도착했을 때 키가 있으면 그대로 진행

3. 없으면 알파벳 문을 위한 큐에 따로 저장

4. 소문자 알파벳에 도착했을 때는 열쇠가 이미 있을 경우는 그대로 진행

5. 없던 경우는 키를 Set에 추가하고 대문자 알파벳 큐에 넣었던 큐를 원래 큐에 추가

6. $인 경우를 찾아서 ans 에 1 추가

 

✅Code

from collections import deque
import sys

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

# sys.stdin = open('D:/test.txt', 'r')

def printa(a):
    for i in a:
        for j in i:
            print(j, end=" ")
        print()
    print()

t = int(input())
for _ in range(t):
    n, m = map(int, input().split())

    a = ["."+input()+"." for _ in range(n)]
    n += 2
    m += 2
    a = ["."*m] + a + ["."*m]

    key = set(input())
    ans = 0
    check = [[False]*m for _ in range(n)]
    q = deque()
    door = [deque() for _ in range(26)]
    q.append((0, 0))
    check[0][0] = True
    while q:
        x, y = q.popleft()
        for k in range(4):
            nx, ny = x+dx[k], y+dy[k]
            if check[ny][nx]:
                continue
            if a[ny][nx] == '*':
                continue
            check[ny][nx] = True
            if a[ny][nx] == '.':
                q.append((nx, ny))
            elif a[ny][nx] == '$':
                q.append((nx, ny))
                ans += 1
            elif 'A' <= a[ny][nx] <= 'Z':
                if a[ny][nx].lower() in key:
                    q.append((nx, ny))
                else:
                    door[ord(a[ny][nx])-ord('A')].append((nx, ny))
            elif 'a' <= a[ny][nx] <= 'z':
                q.append((nx, ny))
                if not a[ny][nx] in key:
                    key.add(a[ny][nx])
                    q.extend(door[ord(a[ny][nx])-ord('a')])
    print(ans)