[bj9328] 열쇠

문제

• 백준 URL: 열쇠
• 난이도 골드 1

풀이

건물의 바깥에서 시작한다는 것은 모든 가장자리를 통해 드나들 수 있음을 나타낸다. 즉, 가장자리를 시작 지점으로 하여 q에 넣어주면 쉽게 구현이 쉬워진다.

    q = deque()
    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 bMap[i][j] == '*': continue
                q.append((i,j))
                visited[i][j] = 1

유의할 점은 시작 지점이 문이던, 열쇠던, 문서던 상관 없이 벽만 아니면 시작 지점으로 선택 가능해야 한다는 점이며 이에 대한 처리는 bfs 함수에서 해주었다.

    next_q = deque()
    while q:
        x,y = q.popleft()
        p = bMap[x][y]
        if 'A' <= p <= 'Z' and p.lower() not in keys:
            next_q.append((x,y))
            continue
        elif p == '$': ans+=1
        elif 'a' <= p <= 'z':
            keys.add(p)
            q.extend(next_q)
            next_q.clear()

bfs 함수의 일부인데 중요한 부분은 문과 마주했을 시 열쇠가 없는 경우 문에서 멈춰섰다고 가정하여 next_q에 해당 좌표를 저장해주고, 열쇠를 얻었을 때 q에 extend 해주어 다시 탐색할 수 있게 해주었다는 점이다. 달이 차오른다, 가자같은 문제와 달리 최적의 이동 횟수를 세는게 아니며 이미 탐색한 부분은 다시 탐색할 필요가 없기 때문에 이렇게 구현해도 된다.

전체 코드는 다음과 같다.

from collections import deque

dir = [(0,1),(1,0),(0,-1),(-1,0)]

def bfs(q):
    global ans
    next_q = deque()
    while q:
        x,y = q.popleft()
        p = bMap[x][y]
        if 'A' <= p <= 'Z' and p.lower() not in keys:
            next_q.append((x,y))
            continue
        elif p == '$': ans+=1
        elif 'a' <= p <= 'z':
            keys.add(p)
            q.extend(next_q)
            next_q.clear()
        for dx,dy in dir:
            nx,ny = x+dx, y+dy
            if 0 <= nx < h and 0 <= ny < w and not visited[nx][ny]:
                if p == '*': continue
                else:
                    q.append((nx,ny))
                    visited[nx][ny] = 1
    
    return next_q

for _ in range(int(input())):
    h,w = map(int, input().split())
    bMap = [[*input()] for _ in range(h)]
    visited = [[0]*w for _ in range(h)]
    keys = set()
    ans = 0
    
    q = deque()
    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 bMap[i][j] == '*': continue
                q.append((i,j))
                visited[i][j] = 1
    
    for i in input(): keys.add(i)
    
    while bfs(q): pass
    print(ans)