[백준 9328번] 파이썬(python) - 열쇠

# 조건

 

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

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

 

입력

• 첫째 줄에 테스트 케이스의 개수가 주어진다. 테스트 케이스의 수는 100개를 넘지 않는다.
• 각 테스트 케이스의 첫째 줄에는 지도의 높이와 너비 h와 w (2 ≤ h, w ≤ 100)가 주어진다.
• 다음 h개 줄에는 빌딩을 나타내는 w개의 문자가 주어지며, 각 문자는 다음 중 하나이다.
  • '.'는 빈 공간을 나타낸다.
  • '*'는 벽을 나타내며, 상근이는 벽을 통과할 수 없다.
  • '$'는 상근이가 훔쳐야하는 문서이다.
  • 알파벳 대문자는 문을 나타낸다.
  • 알파벳 소문자는 열쇠를 나타내며, 그 문자의 대문자인 모든 문을 열 수 있다.
• 마지막 줄에는 상근이가 이미 가지고 있는 열쇠가 공백없이 주어진다.
  • 만약, 열쇠를 하나도 가지고 있지 않는 경우에는 "0"이 주어진다.
• 상근이는 처음에는 빌딩의 밖에 있으며, 빌딩 가장자리의 벽이 아닌 곳을 통해 빌딩 안팎을 드나들 수 있다.
• 각각의 문에 대해서, 그 문을 열 수 있는 열쇠의 개수는 0개, 1개, 또는 그 이상이고, 각각의 열쇠에 대해서, 그 열쇠로 열 수 있는 문의 개수도 0개, 1개, 또는 그 이상이다. 열쇠는 여러 번 사용할 수 있다.

 

# 접근 방법

• 입력을 받고 우선 외벽을 순회해주며 문 또는 빈 공간을 추가해준다.
  • 문이면 x, y, 1로 넣어주고 빈 공간이면 좌표,0 으로 append해준다.
  • 또한 열쇠를 바로 주운 후 key 와 entry에 append
  • 문서면 바로 주워주고 entry에 append
• while문을 돌리며 문서를 찾으러 다닐건데 열쇠를 줍는다면 다시 순회해주어야 하므로 flag 변수를 사용해준다.
  • while문 내부의 for문을 돌리며 빈 공간이면 바로 탐색, 문이라면 열쇠가 있는지 체크해준다.
• def search 함수를 bfs로 탐색해준다.
  • 시작 위치를 popleft로 받아준 후 델타 탐색 해준다.
  • 이 때 범위는 ni, nj는 좌표 크기 내부, visited = 0이며 arr이 벽이 아닌 경우만 탐색해준다.
• 벽이 아닌 경우 나올 수 있는 경우의 수는 4가지이다.
  • 문을 만난 경우 열쇠가 있다면 q에 추가
  • 열쇠를 만난 경우 열쇠를 key에 추가해주고 q에 추가해준 후 arr에서 0으로 변경
  • 문서를 만난 경우 result + 1 해주고 q에 좌표 추가 후 arr 0으로 변경
  • 그냥 길이라면 탐색

import sys  
sys.stdin = open('input.txt')  
input = sys.stdin.readline  
from collections import deque  
  
T = int(input())  
  
di, dj = [1,-1,0,0], [0,0,1,-1]  
# 문서 찾아 떠나는 함수  
def search(start, end):  
    global result, flag  
    q = deque()  
    q.append((start, end))  
    visited[start][end] = 1  
    while q:  
        sti, stj = q.popleft()  
        for i in range(4):  
            ni, nj = sti + di[i], stj + dj[i]  
            # ni, nj가 범위 내에 있고, 방문 하지 않았고, 길이 있다면  
            if 0<=ni<h and 0<=nj<w and visited[ni][nj] == 0 and arr[ni][nj] != '*':  
                # 이 때 문이라면 열쇠 체크  
                if arr[ni][nj].isupper():  
                    if arr[ni][nj].lower() in key:  
                        q.append((ni, nj))  
                        arr[ni][nj] = "."  
                        visited[ni][nj] = 1  
                # 열쇠라면 열쇠 줍고 flag 변화  
                elif arr[ni][nj].islower():  
                    if not arr[ni][nj] in key:  
                        key.append(arr[ni][nj])  
                        flag = True  
                    arr[ni][nj] = "."  
                    q.append((ni, nj))  
                    visited[ni][nj] = 1  
                # 문서라면 문서 줍기  
                elif arr[ni][nj] == '$':  
                    result += 1  
                    visited[ni][nj] = 1  
                    arr[ni][nj] = "."  
                    q.append((ni, nj))  
                else:  
                    q.append((ni, nj))  
                    visited[ni][nj] = 1  
  
  
  
for _ in range(T):  
    h, w = map(int, input().rstrip().split())  
    arr = [list(input().rstrip()) for _ in range(h)]  
    key = list(input().rstrip())  
    entry = []  
    result = 0  
    # 외벽 순회하면서 key와 빈 공간 추가해주기  
    # 1 이면 key 0 이면 빈 공간    
    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 arr[i][j] == '.':  
                    entry.append((i,j, 0))  
                elif 'A' <= arr[i][j] <= 'Z':  
                    entry.append((i, j , 1))  
                elif 'a' <= arr[i][j] <= 'z':  
                    key.append(arr[i][j])  
                    arr[i][j] = '.'  
                    entry.append((i,j,0))  
                elif arr[i][j] == '$':  
                    result += 1  
                    arr[i][j] = '.'  
                    entry.append((i,j, 0))  
  
    # 문서찾으러 다니기  
    # while 문 사용하는데 열쇠를 주울 수 있으므로 flag 사용    
    flag = True  
    cnt = 0  
    while flag:  
        flag = False  
        # 방문기록  
        visited = [[0] * w for _ in range(h)]  
        for i, j, k in entry:  
            if k == 0:  
                search(i, j)  
            elif k == 1 and arr[i][j].lower() in key:  
                search(i,j)  
  
        cnt += 1  
    print(result)