[Python] boj no. 9328 : 열쇠

Problem

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

Idea

제약 조건이 많은 너비 우선 탐색 문제이다.

빌딩 가장자리의 벽이 아닌 곳을 통해 빌딩 안밖을 드나들 수 있다는 조건이 있기 때문에 우선 평면도를 입력받은 후 빈 공간에 해당하는 ‘.’로 리스트를 둘러친 후 탐색을 시작했다.

다음과 같은 기준으로 탐색을 수행했다.

1. 탐색 위치가 이미 방문했거나, 벽(‘*‘)일 경우, 탐색하지 않는다.
2. 탐색 위치가 빈 공간(‘.’)일 경우, 정상적으로 탐색한다.
3. 탐색 위치가 문서(‘.’)일 경우, 결과 값에 +1을 하고 정상적으로 탐색한다. 이 때, 문서를 중복하여 세는 것을 방지하기 위해 문서를 빈 공간으로 변경한다.
4. 탐색 위치가 문(알파벳 대문자)일 경우, 해당 하는 키(알파벳 소문자)가 존재할 경우 탐색하고 존재하지 않는 경우 탐색하지 않는다. 만약 탐색할 경우 해당 공간을 빈 공간으로 변경한다.
5. 탐색 위치가 키(알파벳 소문자)일 경우, 키가 키 집합에 존재하지 않는 경우에만 집합에 추가하고 방문 리스트를 초기화한다. 즉, 탐색을 새로 다시 시작한다. 이후 해당 공간을 빈공간으로 변경하고 탐색한다.

Code

import sys
from collections import deque

def bfs():
    dq = deque()
    dq.append((0, 0))
    visited = [[False for _ in range(w+2)] for _ in range(h+2)]
    visited[0][0] = True
    sol = 0
    
    dy = [-1, 1, 0, 0]
    dx = [0, 0, -1, 1]
    
    while dq:
        cy, cx = dq.popleft()
        
        for i in range(4):
            ny, nx = cy+dy[i], cx+dx[i]
            if 0 <= ny < h+2 and 0 <= nx < w+2 and visited[ny][nx] == False and maze[ny][nx] != '*':
                if maze[ny][nx] == '$':
                    sol += 1
                    maze[ny][nx] = '.'
                elif 'A' <= maze[ny][nx] <= 'Z':
                    if maze[ny][nx].lower() in key:
                        maze[ny][nx] = '.'
                    else:
                        continue
                elif 'a' <= maze[ny][nx] <= 'z':
                    if maze[ny][nx] not in key:
                        key.add(maze[ny][nx])
                        visited = [[False for _ in range(w+2)] for _ in range(h+2)]

                    maze[ny][nx] = '.'                 
                    
                visited[ny][nx] = True
                dq.append((ny, nx))               
    
    return sol

input = sys.stdin.readline
T = int(input())

for _ in range(T):
    h, w = map(int, input().split())
    maze = [[] for _ in range(h+2)]
    maze[0] = ['.'] * (w+2)
    for i in range(1, h+1):
        maze[i] = ['.'] + list(input().rstrip()) + ['.']
    maze[h+1] = ['.'] * (w+2)
    key = set()
    temp = input().strip()
    if temp != '0':
        key = set(temp)     
    
    print(bfs())

Comment

구현 문제는 역시 힘이 빠진다. 익숙해질 수 있도록 자주 풀어야 할 것 같다.