(Python/파이썬) - 백준(BOJ) 9328번 : 열쇠

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

9328번: 열쇠

---

• 문제 : 

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

 

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

 

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

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

 

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

 

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

 

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

 

 

---

• 풀이 :

BFS 문제였습니다.

 

세부적인 사항은 코드에 주석을 달아놓았으니 알고리즘의 큰 흐름만 설명하겠습니다.

 

1. 열쇠를 저장할 key 집합과, 문을 방문했으나 열쇠가 없을 때 그 좌표를 저장할 unlocked_door dict를 사용합니다.

(열쇠가 있는지 여부를 확인할 때 O(1)의 시간복잡도를 갖게 하기 위해set을, 방문했지만 열 수 없는 문들의 좌표를 담기 위해 dict를 사용했습니다.)

 

2. 테두리를 탐색하며 벽이 아닌 경우에 1. 통로인 경우, 2. 열쇠인 경우, 3. 문서인 경우, 4. 문인 경우로 나누어 생각합니다.

 

통로인 경우, 해당 좌표를 가능한 시작좌표들인 start 배열에 넣습니다.

열쇠인 경우,  해당 좌표의 값(열쇠의 알파벳)을 key 집합에 넣고 해당 좌표를 start 배열에 넣습니다.

문서인 경우,  해당 좌표를 start 배열에 넣고 answer 카운트를 1 증가시킵니다.

문인 경우,  unlocked_door에 해당 좌표를 넣습니다.

 

3. 모든 테두리를 탐색한 뒤 현재 갖고있는 열쇠에 대해 unlocked_door에 열 수 있는 문이 있는지 찾은 후 start 배열에 넣습니다.

 

4. start의 모든 시작좌표에 대해 bfs를 실시합니다. bfs는 상, 하, 좌, 우로 탐색하여 테두리를 탐색할 때와 마찬가지로 4가지 경우로 나누어 처리합니다. 테두리를 탐색할 때와 다른 점은, 문을 방문한 경우 해당 문의 열쇠를 갖고 있는지 확인한 후 갖고있다면 방문하고 아니라면 unlocked_door에 넣는 것입니다. ( 테두리에서는 무조건 unlocked_door에 넣음)

또한, 열쇠가 있는 좌표를 방문한 경우엔 해당 열쇠가 열 수 있는 문이 있는지 unlocked_door에서 확인하고 있다면 해당 좌표를 queue에 넣습니다.

 

 

 

 

 

 

---

• 소스코드 : 

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

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

def bfs(start):
    global answer
    queue = deque()
    queue.append(start)
    while queue:
        x,y = queue.popleft()
        for i in range(4):
            ax = x + dx[i]
            ay = y + dy[i]
            if 0 <= ax < H and 0 <= ay < W and board[ax][ay] != "*" and not visited[ax][ay]: #방문할 수 있는 경우
                if board[ax][ay].isupper(): # 문인 경우
                    if board[ax][ay] in key: # 열쇠가 있다면 방문
                        queue.append([ax, ay])
                        visited[ax][ay] = True
                    else: # 열쇠가 없다면 미방문 좌표로 저장
                        unlocked_door[board[ax][ay]].append([ax, ay])
                else: # 통로, 문서, 열쇠인 경우
                    queue.append([ax,ay])
                    visited[ax][ay] = True
                    if board[ax][ay] == "$": # 문서인 경우
                        answer += 1
                    if board[ax][ay].islower(): # 열쇠인 경우
                        key.add(board[ax][ay].upper()) # 열쇠흘 저장
                        for x1, y1 in unlocked_door[board[ax][ay].upper()]: # 해당 열쇠로 열 수 있는 미방문 좌표를 방문
                            queue.append([x1, y1])
                            visited[x1][y1] = True


for _ in range(int(input())):
    answer = 0
    H,W = map(int,input().split())
    board = [list(input().strip()) for _ in range(H)]
    key = set()
    unlocked_door = dict()
    for alphabet in ascii_uppercase:
        unlocked_door[alphabet] = []
    start = []
    for k in input().strip():
        if k == "0":
            break
        key.add(k.upper())
    visited = [[False for _ in range(W)] for _ in range(H)]
    for i in range(H):
        for j in range(W):
            if i == 0 or i == H-1 or j == 0 or j == W-1: # 테투리인 경우
                if board[i][j] != "*":
                    if board[i][j].isupper(): # 문인 경우 미방문 좌표로 저장
                        unlocked_door[board[i][j]].append([i, j])
                    else: # 아닌 경우 문서, 열쇠, 통로의 경우로 나누어서 처리
                        if board[i][j] == "$":
                            answer += 1
                        elif board[i][j].islower():
                            key.add(board[i][j].upper())
                        start.append([i,j])
                        visited[i][j] = True
    for k in key: # 지금 갖고있는 열쇠로 방문할 수 있는 미방문 좌표 탐색
        for x,y in unlocked_door[k]:
            start.append([x,y])
            visited[x][y] = True
    for s in start: # 테두리의 가능한 시작좌표에 대해 탐색시작
        bfs(s)
    print(answer)