[백준] 9328. 열쇠 - Python

[Gold I]

 

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

9328번: 열쇠

 

풀이

시간초과와 메모리 초과를 몇 번 받다가, 이리저리 최적화하여 Accepted 받은 문제.

 

처음엔 [백준] 1194. 달이 차오른다, 가자. 와 비슷해 보여, 비슷하게 Bitmasking을 이용해 풀이할까 생각했지만,

가능한 열쇠의 개수가 26개이므로, 2^26의 경우의 수를 모두 저장할 수는 없어, 다른 방법을 생각했다.

---

우선 그래프(지도)의 형태를 입력받을 때, 겉을 빈 공간('.')으로 둘러싼다. (line 10~14)

빌딩 가장자리의 벽이 아닌 곳을 통해 빌딩 안팎을 드나들 수 있으므로, 좌표 (0, 0)부터 시작하여 BFS로 진행할 시, 가장자리의 벽이 아닌 모든 곳에 도달할 수 있게 하기 위함.

 

열쇠 보유 여부는 길이가 26(a~z)인 배열에 0, 1 state로 저장한다. (line 16)

 

이후, 여느 시뮬레이션/구현 BFS 문제와 비슷하게 BFS로 탐색하며 진행하면 되는데, 문에 다다랐을 때, 문에 대한 열쇠가 없다면, 문의 위치를 임시로 저장한 후에, 대응하는 열쇠를 얻었을 때 다시 queue에 append하여 진행한다. (line 41~51)

 

마지막으로, visited 처리는 지나간 칸을 벽('*')으로 변경하며 진행하는 것으로 처리했다.

 

AC.

from collections import deque

T = int(input())
results = []

for _ in range(T):
    h, w = map(int, input().split())

    # 입력
    graph = []
    graph.append(["." for _ in range(w+2)])
    for _ in range(h):
        graph.append(list("."+input()+"."))
    graph.append(["." for _ in range(w+2)])

    keys = [0 for _ in range(26)]  # a~z : 0 초기화
    for k in list(input()):
        if k != "0":
            keys[ord(k) - 97] = 1
            
    # BFS
    dr = [1, 0, -1, 0]
    dc = [0, 1, 0, -1]

    deq = deque([(0,0)])

    papers = 0
    tempDoors = [[] for _ in range(26)]  # A~Z : [] 초기화

    while deq:
        r, c = deq.popleft()
        
        # 상하좌우 방문 확인 및 queue append
        for i in range(4):
            nr = r + dr[i]
            nc = c + dc[i]
            
            if 0 <= nr < h+2 and 0 <= nc < w+2 and graph[nr][nc] != "*":
                # 방문 처리 및 방문한 곳의 상태에 대한 업데이트
                num = ord(graph[nr][nc])
                if 65 <= num <= 90:    # 문
                    # 열쇠가 없는 상태면, 문을 임시 저장
                    if keys[num - 65] == 0:
                        tempDoors[num - 65].append((nr, nc))
                        continue
                elif 97 <= num <= 122:   # 열쇠
                    # 열쇠가 새로 추가된다면, 임시 저장한 문을 꺼내 deq 맨 위에 push
                    if keys[num - 97] == 0:
                        for door in tempDoors[num - 97]:
                            deq.appendleft(door)
                    keys[num - 97] = 1
                elif graph[nr][nc] == "$":  # 서류
                    papers += 1
                
                graph[nr][nc] = "*"
                
                deq.append((nr, nc))
            
    results.append(papers)
    
for r in results:
    print(r)