9328: 열쇠

풀이 시간

• 1h 20m
• 열쇠를 발견했을 경우 queue와 visit리스트를 초기화하는 아이디어를 참고했다

구현 방식

• "상근이는 처음에는 빌딩의 밖에 있으며, 빌딩 가장자리의 벽이 아닌 곳을 통해 빌딩 안팎을 드나들 수 있다."라는 설명을 통해 board의 가장자리를 모두 '.'로 채워주고 H+=2; W+=2를 수행해주었다

• bfs를 통해 2차원 이동을 수행하면서 max_docs_cnt를 구해주었다.

  • 무한 루프를 돌지 않기 위해선 visit 리스트를 사용해야 하는데, 이 문제에서는 방문 했던 곳을 다시 방문해야하는 경우가 발생할 수 있기 때문에 단순하게 visit 리스트를 사용해서는 안된다
  • 열쇠를 발견한 경우에 queue와 visit리스트를 초기화해주어야 한다

1. 빈 공간
   -> visit True로 갱신
   -> queue에 노드 append

2. 열쇠
   -> keys set에 열쇠 추가
   -> board '.'으로 갱신
   -> queue 초기화
   -> visit 초기화
   -> queue에 노드 append

3. 문
   해당하는 key가 있는 경우,
   -> visit True로 갱신
   -> board '.'으로 갱신
   -> queue에 노드 append

4. 문서
   -> max_docs_cnt 1 증가
   -> visit True로 갱신
   -> board '.'로 갱신
   -> queue에 노드 append

코드

import sys
from collections import deque

dx = (0, 0, -1, 1)
dy = (-1, 1, 0, 0)

def bfs(x, y):
    global max_docs_cnt, keys

    queue = deque([]); queue.append((x, y))
    visit = [[False] * W for h in range(H)]; visit[x][y] = True

    while queue:
        x, y = queue.popleft()
        for i in range(4):
            nx = x + dx[i]; ny = y + dy[i]
            if 0 <= nx < H and 0 <= ny < W:
                if not visit[nx][ny]:
                    if board[nx][ny] == '.': #빈 공간
                        visit[nx][ny] = True
                        queue.append((nx, ny))

                    elif 97 <= ord(board[nx][ny]) <= 122: #열쇠 -> queue 초기화, visit 리스트 초기화
                        keys.add(board[nx][ny])
                        board[nx][ny] = '.'
                        queue = deque([])
                        visit = [[False] * W for h in range(H)]; visit[nx][ny] = True
                        queue.append((nx, ny))

                    elif 65 <= ord(board[nx][ny]) <= 90: #문
                        if chr(ord(board[nx][ny]) + 32) in keys:
                            visit[nx][ny] = True
                            board[nx][ny] = '.'
                            queue.append((nx, ny))

                    elif board[nx][ny] == '$': #문서
                        max_docs_cnt += 1
                        visit[nx][ny] = True
                        board[nx][ny] = '.'
                        queue.append((nx, ny))


T = int(sys.stdin.readline()[:-1])
for t in range(T):
    H, W = map(int, sys.stdin.readline()[:-1].split())

    board = deque([])
    for h in range(H):
        board.append(deque(list(sys.stdin.readline()[:-1])))
    
    keys = set(list(sys.stdin.readline()[:-1]))

    for i in range(H):
        board[i].appendleft('.'); board[i].append('.')
    board.appendleft(deque(['.' for w in range(W+2)])); board.append(deque(['.' for w in range(W+2)]))

    H += 2; W += 2
    max_docs_cnt = 0
    bfs(0, 0)
    
    print(max_docs_cnt)

결과