백준(BOJ) 9328 열쇠(Python)

문제 내용

 

BFS 문제.

고려해줄 게 많아서 좀 귀찮았다.

 

먼저 맵을 확장시켜줬다.

시작을 건물 밖에서 하거니와 건물의 어떤 방향으로도 입장할 수 있기 때문에 (w+2)*(h+2) 크기로 맵을 확장시킨 후 가장자리를 모두 '.'로 둘렀다. 코딩을 처음 시작할 때 이런저런 문제를 풀면서 이미 해봤던 방법이라 쉽게 떠올릴 수 있었다.

그 후에는 현재 가진 키를 통해 갈 수 있는 문을 체크하는 배열을 만들고, BFS를 진행했다.

이미 지나온 오브젝트는 모두 '.'으로 만들어주고, 만약 열쇠를 주운 경우에는 visited와 queue를 초기화해줬다.

왜냐하면, 열쇠를 새로 줍는 순간 기존에는 갈 수 없었던 곳을 갈 수 있게 되어 이미 지나왔던 곳을 모두 다시 가봐야하기 때문이다.

 

코드는 다음과 같다.

 

# -*- coding: utf-8 -*-
import sys
from collections import deque
import heapq
import copy
#input=sys.stdin.readline
#sys.setrecursionlimit(100000000)

t=int(input())
dx=[1,-1,0,0]
dy=[0,0,1,-1]
for i in range(t):
    h,w=map(int,input().split())
    L=[['.' for j in range(w+2)] for k in range(h+2)]
    for j in range(1,h+1):
        L[j][1:w+1]=list(input())
    key=input()
    d=[0]*26
    if key!='0':
        for j in key:
            d[ord(j)-ord('a')]=1
    visited=[[0 for j in range(w+2)] for k in range(h+2)]
    queue=deque()
    queue.append([0,0])
    visited[0][0]=1
    ans=0
    while queue:
        x,y=queue.popleft()
        for k in range(4):
            nx=x+dx[k]
            ny=y+dy[k]
            if 0<=nx<h+2 and 0<=ny<w+2:
                if not visited[nx][ny]:
                    if L[nx][ny]=='.':
                        visited[nx][ny]=1
                        queue.append([nx,ny])
                    elif L[nx][ny]=='$':
                        visited[nx][ny]=1
                        L[nx][ny]='.'
                        ans+=1
                        queue.append([nx,ny])
                    elif L[nx][ny].isupper():
                        if d[ord(L[nx][ny])-ord('A')]:
                            visited[nx][ny]=1
                            L[nx][ny]='.'
                            queue.append([nx,ny])
                    elif L[nx][ny].islower():
                        d[ord(L[nx][ny])-ord('a')]=1
                        L[nx][ny]='.'
                        visited=[[0 for i in range(w+2)] for j in range(h+2)]
                        visited[nx][ny]=1
                        queue=deque()
                        queue.append([nx,ny])
    print(ans)

코드가 길고 고려해줘야 할 부분이 많지만 생각보다 시간복잡도가 크지 않아서 python으로 제출해도 통과했다.