[백준] 9328 - 열쇠 (G1)

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

9328번: 열쇠

BFS를 응용한 단순 구현문제이다.

 

내가 푼 알고리즘은 다음과 같다.

 

1. 외곽을 모두 돌면서 빈공간의 위치를 덱에 넣고,

열쇠는 먹은 후 빈공간으로 바꾼다음 위치를 덱에 넣고,

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

(이때 같은 문이 여러개 있을 수 있으니, 맵에 리스트를 저장한다.)

(열쇠는 같은 열쇠가 여러개 있을 수 있으니 집합에 저장한다.)

 

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

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

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

 

3. 덱에 저장된 내용으로 BFS를 돌린다.

 

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

 

5. BFS가 끝나기 직전에는 (덱에 아무 내용도 없을 때)

현재 갈 수 있는 모든 곳을 다 순회하면서 먹을 수 있는 열쇠도 다 먹은 상태이다.

이 상태에서 다시 모든 문을 열고 문 정보를 맵에서 제거하고 문위치를 덱에 넣어

열린 문에서부터 다시 BFS를 돈다.

 

이 과정을 반복하면서 중간 중간 만난 비밀문서의 개수를 센다.

 

import sys
from collections import deque
input = sys.stdin.readline

TEST_MODE = True
dh = [0, 0, 1, -1]
dw = [-1, 1, 0, 0]

def printBoard(_board):
    global h

    if not TEST_MODE:
        return

    for ii in range(h):
        print(_board[ii])
    print()


def openAllDoor():
    for key in keys:
        while doors[key.upper()]:
            door_h, door_w = doors[key.upper()].pop()
            board[door_h][door_w] = '.'
            d.append((door_h, door_w))
            visit[door_h][door_w] = True


t = int(input())
for _ in range(t):
    h, w = map(int, input().split())
    board = []
    for __ in range(h):
        board.append(list(input().rstrip()))

    keys = list(input().rstrip())
    if keys[0] == '0':
        keys = set()
    else:
        keys = set(keys)

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

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

    #print(doors)

    answer = 0

    # 외곽을 체크하면서 빈공간 찾기, 첫 외곽을 돌 때는 방문 배열이 모두 false 이므로 체크할 필요가 없다.
    for i in range(h):
        for j in range(w):
            if 0 < i < h-1 and 0 < j < w-1:
                continue
            if board[i][j] == '*':
                continue

            if board[i][j] == '.':
                d.append((i, j))
                visit[i][j] = True
            elif board[i][j] == '$':
                answer += 1
                board[i][j] = '.'
                d.append((i, j))
                visit[i][j] = True
            elif 'a' <= board[i][j] <= 'z':
                keys.add(board[i][j])
                board[i][j] = '.'
                d.append((i, j))
                visit[i][j] = True
            elif 'A' <= board[i][j] <= 'Z':
                # 문은 지금 열 수 있어도 바로 열지 않고, 모든 외곽 체크를 끝내고 열쇠를 먹은 만큼 다 먹고나면 그때부터 문 열기.
                # 지금 열면 구현할 때 실수하기 쉬워진다.
                doors[board[i][j]].append((i, j))

    # 문열기
    openAllDoor()

    while d:
        now_h, now_w = d.popleft()

        for k in range(4):
            check_h = now_h + dh[k]
            check_w = now_w + dw[k]
            if 0 <= check_h < h and 0 <= check_w < w:
                if board[check_h][check_w] == "." and not visit[check_h][check_w]:
                    d.append((check_h, check_w))
                    visit[check_h][check_w] = True
                elif board[check_h][check_w] == "$":
                    answer += 1
                    board[check_h][check_w] = '.'
                    d.append((check_h, check_w))
                    visit[check_h][check_w] = True
                elif 'a' <= board[check_h][check_w] <= 'z':  # 열쇠가 있다는 것은 방문하지 않았다. (방문후에는 빈칸으로 바꾸고 있으니까)
                    keys.add(board[check_h][check_w])
                    board[check_h][check_w] = '.'
                    d.append((check_h, check_w))
                    visit[check_h][check_w] = True
                elif 'A' <= board[check_h][check_w] <= 'Z':  # 문을 만나면 문을 저장
                    doors[board[check_h][check_w]].append((check_h, check_w))

        # 만약 방문을 다 해서 덱이 비어있다면, BFS가 끝났으므로 문을 열고 연 위치부터 이어서 다시 BFS 진행
        if not d:
            openAllDoor()

    print(answer)