백준 9328번 열쇠

문제

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

상근이가 훔칠 수 있는 문서의 최대 개수를 구하는 프로그램을 작성하시오.

입력

첫째 줄에 테스트 케이스의 개수가 주어진다. 테스트 케이스의 수는 100개를 넘지 않는다.

각 테스트 케이스의 첫째 줄에는 지도의 높이와 너비 h와 w (2 ≤ h, w ≤ 100)가 주어진다. 다음 h개 줄에는 빌딩을 나타내는 w개의 문자가 주어지며, 각 문자는 다음 중 하나이다.

• '.'는 빈 공간을 나타낸다.
• '*'는 벽을 나타내며, 상근이는 벽을 통과할 수 없다.
• '$'는 상근이가 훔쳐야하는 문서이다.
• 알파벳 대문자는 문을 나타낸다.
• 알파벳 소문자는 열쇠를 나타내며, 그 문자의 대문자인 모든 문을 열 수 있다.

마지막 줄에는 상근이가 이미 가지고 있는 열쇠가 공백없이 주어진다. 만약, 열쇠를 하나도 가지고 있지 않는 경우에는 "0"이 주어진다.

상근이는 처음에는 빌딩의 밖에 있으며, 빌딩 가장자리의 벽이 아닌 곳을 통해 빌딩 안팎을 드나들 수 있다. 각각의 문에 대해서, 그 문을 열 수 있는 열쇠의 개수는 0개, 1개, 또는 그 이상이고, 각각의 열쇠에 대해서, 그 열쇠로 열 수 있는 문의 개수도 0개, 1개, 또는 그 이상이다. 열쇠는 여러 번 사용할 수 있다.

출력

각 테스트 케이스 마다, 상근이가 훔칠 수 있는 문서의 최대 개수를 출력한다.

 

2. 코드

 

import sys
from collections import deque

input = sys.stdin.readline

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

def openAllDoor():
    for key in keys:
        while doors[key.upper()]:
            x, y = doors[key.upper()].pop()
            maps[x][y] = '.'
            queue.append((x, y))
            visit[x][y] = True

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

    maps = [list(input().rstrip()) for _ in range(h)]

    keys = list(input().rstrip())

    if keys[0] == '0':
        keys = set()
    else:
        keys = set(keys)

    queue = deque()
    visit = [[False for _ in range(w)] for _ in range(h)]

    doors = {}
    for c in list('ABCDEFGHIJKLMNOPQRSTUVWXYZ'):
        doors[c] = []

    answer = 0

    for i in range(h):
        for j in range(w):
            if 0 < i < h - 1 and 0 < j < w - 1:
                continue
            if maps[i][j] == '*':
                continue

            if maps[i][j] == '.':
                queue.append((i, j))
                visit[i][j] = True
            elif maps[i][j] == '$':
                answer += 1
                maps[i][j] = '.'
                queue.append((i, j))
                visit[i][j] = True
            elif 'a' <= maps[i][j] <= 'z':
                keys.add(maps[i][j])
                maps[i][j] = '.'
                queue.append((i, j))
                visit[i][j] = True
            elif 'A' <= maps[i][j] <= 'Z':
                doors[maps[i][j]].append((i, j))

    openAllDoor()

    while queue:
        x, y = queue.popleft()

        for i in range(4):
            nx = x + dx[i]
            ny = y + dy[i]

            if 0 <= nx < h and 0 <= ny < w:

                if maps[nx][ny] == "." and not visit[nx][ny]:
                    queue.append((nx, ny))
                    visit[nx][ny] = True
                elif maps[nx][ny] == "$":
                    answer += 1
                    maps[nx][ny] = '.'
                    queue.append((nx, ny))
                    visit[nx][ny] = True

                elif 'a' <= maps[nx][ny] <= 'z':
                    keys.add(maps[nx][ny])
                    maps[nx][ny] = '.'
                    queue.append((nx, ny))
                    visit[nx][ny] = True

                elif 'A' <= maps[nx][ny] <= 'Z':
                    doors[maps[nx][ny]].append((nx, ny))


        if not queue:
            openAllDoor()

    print(answer)

 

3. 문제 해결법

1. 외곽을 모두 돌면서 빈공간의 위치를 queue에 넣고, 열쇠는 먹은 후 빈공간으로 바꾼다음 위치를 queue에 넣고,

    문은 맵에 문 위치를 저장한다.

 

2. 현재 갖고 있는 열쇠로 열 수 있는 문을 모두 연다.

    문을 열고나면 해당 공간을 빈 공간으로 만들고, 그 위치를 queue에 넣는다.

    열린 문은 맵에서 제거한다.

 

3. BFS를 돌린다.

 

4. BFS를 돌면서 지나갈 수 있는 모든 곳을 지나가며 열쇠를 먹는다.

 

5.BFS가 끝나기 직전에 현재 갈 수 있는 모든 곳을 다 순회하면서 먹을 수 있는 열쇠도 다 먹은 상태이다.이 상태에서 다시 모든 문을 열고 문 정보를 맵에서 제거하고 문위치를 queue에 넣어 열린 문에서부터 다시 BFS를 돈다.