백준 9328 : 열쇠

BFS 를 이용한 구현 문제
단, 테스트 케이스가 최대 100개 주어지기 때문에 가능한 연산 횟수는 약 10만번 정도이다.

📜 문제 바로 가기 : 백준 열쇠

제출 코드

import sys
input = sys.stdin.readline

from collections import defaultdict
from collections import deque

def isGo(i, j):
    if 0 <= i < N and 0 <= j < M and arr[i][j] != "*" and not visited[i][j]:
        return True
    return False

def isDoor(i, j):
    global ans
    v = arr[i][j]
    if arr[i][j] == "$":
        ans += 1
        return False
    
    if arr[i][j] == ".":
        return False
    key = v.lower()
    if v.isupper(): # 문 인경우
        if keyIndex[ord(key) - 97]: # 문인데 키를 보유중이라면
            return False # 문이 없다고 취급함
        goForKey[key].append((i, j)) # key 를 가지고 갈 수 있는 좌표 리스트
        return True
    else: # 키인 경우
        keys.append(v)
        keyIndex[ord(key) - 97] = True
        return False

def BFS(i, j):
    if visited[i][j]:
        return 
    que = deque([(i, j)])
    visited[i][j] = True

    while que:
        i, j = que.popleft()
        for di, dj in delta:
            mi, mj = i+di, j+dj
            if isGo(mi, mj) and not isDoor(mi, mj):
                visited[mi][mj] = True
                que.append((mi, mj))            

delta = [(1,0), (-1,0), (0,1), (0,-1)]
TC = int(input())
for _ in range(TC):
    N, M = map(int, input().split())
    arr = [list(input().rstrip()) for _ in range(N)]
    keys = list(input().rstrip())
    goForKey = defaultdict(list) # 키를 가지고 갈 수 있는 곳 "c" : [(i, j) ... ]

    visited = [[False] *M for _ in range(N)]

    keyIndex = [False] * 26 # 키 보유여부 Index
    for key in keys:
        if key == "0":
            continue
        idx = ord(key) - 97
        keyIndex[idx] = True

    ans = 0
    keys = deque() # 키 리스트 재정의
    # 추가 키없이 갈 수 있는 곳 확인 (테두리만)
    for i in range(N):
        for j in range(0, M, M-1):
            if isGo(i, j) and not isDoor(i, j):
                BFS(i, j)

    for j in range(M):
        for i in range(0, N, N-1):
            if isGo(i, j) and not isDoor(i, j):
                BFS(i, j)

    while keys:
        key = keys.popleft()
        for i, j in goForKey[key]:
            BFS(i, j)
    
    print(ans)

defaultdict 와 deque 를 사용했다.

---

접근한 방법

BFS 순회는 하는데 열쇠를 나중에 얻는 경우를 생각해 봐야 했다. 열쇠를 얻을때마다 처음부터 BFS 를 돌린다면, 배열의 크기가 100 x 100 이기 때문에 무조건 시간초과가 날 것이라고 생각했다.

그래서 생각을 한게 "문"을 만나면 dictionary 형태로 저장하는것
예를 들어 BFS 를 돌다가 (i,j) 에서 문 F를 만났다면 그리고 그 문을 지금 가지고 있는 열쇠로 열수 없다면

# goForKey
{
	"F" : [ (i, j) ]
}

형태로 저장했다.

이런식으로 저장하다가 열쇠를 줍게 되면 열 수 있는 문의 좌표값을 찾아 다시 그 곳 부터 BFS 를 시작한다.

반대로 문이 아닌 열쇠를 줍게 된다면
열쇠는 알파벳 문자 26개로 정해져 있기 때문에 알파벳을 인덱스 값으로 치환하여 리스트에 Boolean 값으로 저장했다.

예를 들어 키 "a" 를 획득 했다면 문자열 "a" 의 아스키코드 정수값이 97 이므로 -97 을 해줘서 0 인덱스 값을 True 로 바꿔준다.

---

코드에서 만든 함수를 살펴보자!

isGo

def isGo(i, j):
    if 0 <= i < N and 0 <= j < M and arr[i][j] != "*" and not visited[i][j]:
        return True
    return False

BFS 순회시에 배열의 범위와 벽, 방문여부(visited)를 체크하여 방문가능한지 확인해 주는 함수이다.

---

isDoor

def isDoor(i, j):
    global ans
    v = arr[i][j]
    if arr[i][j] == "$":
        ans += 1
        return False
    
    if arr[i][j] == ".":
        return False
    key = v.lower()
    if v.isupper(): # 문 인경우
        if keyIndex[ord(key) - 97]: # 문인데 키를 보유중이라면
            return False # 문이 없다고 취급함
        goForKey[key].append((i, j)) # key 를 가지고 갈 수 있는 좌표 리스트
        return True
    else: # 키인 경우
        keys.append(v)
        keyIndex[ord(key) - 97] = True
        return False

이번 문제의 핵심이라고 할 수 있을 거 같다.
isUpper() 함수를 사용하여 대소문자를 판별하였고 열쇠인경우 열쇠등록, 문 인경우 goForKey 에 추가를 해준다.
리턴값은 Boolean 값으로 True 인 경우는 "막혀있다" 라고 판단 하며 False 인 경우는 "지나갈 수 있다." 라고 판단한다.

---

BFS

def BFS(i, j):
    if visited[i][j]:
        return 
    que = deque([(i, j)])
    visited[i][j] = True

    while que:
        i, j = que.popleft()
        for di, dj in delta:
            mi, mj = i+di, j+dj
            if isGo(mi, mj) and not isDoor(mi, mj):
                visited[mi][mj] = True
                que.append((mi, mj))  

일반적인 BFS 방법과 크게 다르지 않으므로 넘어 가겠다!