9328 열쇠

🏅 9328 열쇠

문제

---

상근이는 1층 빌딩에 침입해 매우 중요한 문서를 훔쳐오려고 한다. 상근이가 가지고 있는 평면도에는 문서의 위치가 모두 나타나 있다. 빌딩의 문은 모두 잠겨있기 때문에, 문을 열려면 열쇠가 필요하다. 상근이는 일부 열쇠를 이미 가지고 있고, 일부 열쇠는 빌딩의 바닥에 놓여져 있다. 상근이는 상하좌우로만 이동할 수 있다.
상근이가 훔칠 수 있는 문서의 최대 개수를 구하는 프로그램을 작성하시오.

입력

---

• . : 빈 공간
• * : 벽
• $ : 훔쳐야하는 문서
• 알파벳 대문자와 소문자 : 소문자는 대문자(문)을 열기 위한 열쇠

분석

---

문제에서 상근이는 처음에는 빌딩의 밖에 있으며, 빌딩 가장자리의 벽이 아닌 곳을 통해 빌딩 안팎을 드나들 수 있다. 라고 했으므로 주어진 평면도를 상하좌우로 한 칸씩 늘려야 한다.
먼저 상근이가 갖고 있는 열쇠로 평면도에 있는 문을 다 열어놓는다.
bfs로 탐색하면서, 열쇠를 찾는 경로와 문을 열 수 있는 경로가 겹칠 수 있으므로 열쇠를 찾을 때마다 visited 배열과 큐를 초기화 시켜준다.
열쇠와 문서를 찾았다면 빈 공간(.)으로 변경시켜주고, 문을 열었을 때에도 빈 공간으로 바꿔준다.
$가 있는 칸에 도착하면 cnt 값을 증가시켜주면 된다.

소스 코드

---

import sys
import string
from collections import deque, defaultdict
input = sys.stdin.readline

def bfs(x = 0, y = 0):
    q = deque()
    visited = [[False for _ in range(w+2)] for _ in range(h+2)]
    visited[x][y] = True
    q.append((x, y))

    res = 0
    while q:
        x, y = q.popleft()

        for nx, ny in (x-1, y), (x+1, y), (x, y+1), (x, y-1):
            if nx < 0 or ny < 0 or nx >= h + 2 or ny >= w + 2:
                continue

            if not visited[nx][ny]:
                if board[nx][ny] == '.':
                    q.append((nx, ny))

                elif board[nx][ny] == '$': # 훔칠 물건
                    res += 1
                    board[nx][ny] = '.' # 물건을 훔쳐서 빈 공간이 됨
                    q.append((nx, ny))

                elif board[nx][ny].islower(): # key
                    door[board[nx][ny].lower()] = True # 열쇠를 얻음
                    q.clear()
                    visited = [[False for _ in range(w+2)] for _ in range(h+2)]
                    q.append((nx, ny))
                    board[nx][ny] = '.' # 열쇠를 얻었으므로 빈 공간

                elif board[nx][ny].isupper(): # door
                    if door[board[nx][ny].lower()]: # 키를 갖고 있을 경우
                        visited[nx][ny] = True
                        q.append((nx, ny))
                        board[nx][ny] = '.' # 문을 열음
                visited[nx][ny] = True

    print(res)

for _ in range(int(input())):
    h, w = map(int, input().split())

    # 빌딩 밖에서 접근이 가능하므로 한칸씩 상하좌우 확장
    board = [['.' for _ in range(w+2)]]
    for _ in range(h):
        tmp = ['.']
        tmp.extend(list(input().strip()))
        tmp.extend('.')
        board.append(tmp)
    board.append(['.' for _ in range(w+2)])

    my_keys = list(input().strip())
    door = defaultdict(bool)
    for alphabet in list(string.ascii_lowercase):
        door[alphabet] = False

    if my_keys[0] != '0':
        for key in my_keys:
            door[key] = True

    # 먼저 가진 키로 문을 다 열어 놓는다.
    for i in range(h):
        for j in range(w):
            if board[i][j].isalpha() and board[i][j].isupper():
                if door[board[i][j].lower()]:
                    board[i][j] = '.'

    bfs()