백준 9328 열쇠 (파이썬)

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

9328번: 열쇠

입구를 찾는게 까다로운데 다른 사람의 코드를 보고 쉬운 방법을 알게 되었다

지도의 외곽에 . 을 추가한 후 (0,0)에서 bfs를 시작하면 입구를 따로 구할 필요가 없어 쉽게 풀 수 있다 

 

1. 현재 보유한 열쇠를 입력받고 열쇠에 해당하는 문을 지워둔다

2. 지도에 외곽에 . 을 추가하여 (w+2, h+2) 크기의 행렬로 만들어준 후 (0,0)에서 bfs를 실행

3. 다음칸이 소문자이면 보유한 열쇠를 기록하는 door에 저장하고 소문자에서 . 으로 바꿔준다

   큐와 check 리스트를 초기화한 후 다음 값을 큐에 넣는다 

4. 대문자면 door을 검사하여 열쇠가 있는지 확인 후 이동한다. 이동할 수 있으으면 대문자에서 . 으로 바꿔준다

5. $면 cnt를 증가시키고 . 으로 바꿔준다

from collections import deque
import sys

input = sys.stdin.readline
dx = [1, -1, 0, 0]
dy = [0, 0, 1, -1]

def bfs(x, y):
    q = deque()
    c = [[0]*(w+2) for _ in range(h+2)]
    q.append([x, y])
    c[x][y] = 1
    cnt = 0
    while q:
        x, y = q.popleft()
        for i in range(4):
            nx = x + dx[i]
            ny = y + dy[i]
            if 0 <= nx < h+2 and 0 <= ny < w+2:
                if not c[nx][ny]:
                    if a[nx][ny] == '.':
                        c[nx][ny] = 1
                        q.append([nx, ny])
                    elif a[nx][ny].islower():
                        door[ord(a[nx][ny]) - ord('a')] = 1
                        q = deque()
                        c = [[0]*(w+2) for _ in range(h+2)]
                        a[nx][ny] = '.'
                        q.append([nx, ny])
                    elif a[nx][ny].isupper():
                        if door[ord(a[nx][ny]) - ord('A')]:
                            c[nx][ny] = 1
                            a[nx][ny] = '.'
                            q.append([nx, ny])
                    elif a[nx][ny] == '$':
                        c[nx][ny] = 1
                        cnt += 1
                        a[nx][ny] = '.'
                        q.append([nx, ny])
    print(cnt)

def new_map():
    for i in a:
        i.insert(0, '.')
        i.append('.')
    a.insert(0, ['.']*(w+2))
    a.append(['.']*(w+2))

tc = int(input())
while tc:
    h, w = map(int, input().split())
    a = [list(input().strip()) for _ in range(h)]
    key = list(input().strip())
    door = [0]*26

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

    for i in range(h):
        for j in range(w):
            if ord('A') <= ord(a[i][j]) <= ord('Z'):
                if door[ord(a[i][j]) - ord('A')]:
                    a[i][j] = '.'
    new_map()
    bfs(0, 0)
    tc -= 1