백준 9328. 열쇠

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

import sys
from collections import deque

input = sys.stdin.readline

def bfs(h, w, building, keys):
    directions = [(-1, 0), (1, 0), (0, -1), (0, 1)]
    queue = deque()
    visited = [[False] * w for _ in range(h)]
    key_set = set(keys)  # 열쇠를 저장할 집합(중복 방지를 위해 set 사용)
    door_dict = {chr(i): [] for i in range(ord('A'), ord('Z') + 1)}  # 대문자 문과 위치 저장
    doc_count = 0  # 문서 개수

    # 자주 이용할 친구니까 함수로 만들어놓기
    def add_to_queue(x, y):
        if visited[x][y]:
            return
        visited[x][y] = True
        queue.append((x, y))

    #  1. 가장자리에서 시작 가능한 곳 찾기
    for i in range(h):
        for j in [0, w - 1]:  # 좌우 가장자리
            if building[i][j] != '*':  # 벽이 아니라면(= 빈공간,열쇠,문,문서)
                add_to_queue(i, j)

    for j in range(w):
        for i in [0, h - 1]:  # 상하 가장자리
            if building[i][j] != '*':
                add_to_queue(i, j)

    #  2. BFS 탐색 시작
    while queue:
        x, y = queue.popleft()
        cell = building[x][y]

        if cell == '$':  # 문서 발견
            doc_count += 1

        elif 'a' <= cell <= 'z':  # 열쇠 발견
            key_set.add(cell)
            if cell.upper() in door_dict:  # 해당하는 문이 대기 중이라면
                for (dx, dy) in door_dict[cell.upper()]:  # 큐에 추가
                    queue.append((dx, dy))
                door_dict[cell.upper()] = []

        elif 'A' <= cell <= 'Z':  # 문 발견
            if cell.lower() in key_set:  # 열쇠가 있으면 바로 통과
                pass
            else:  # 열쇠가 없으면 대기
                door_dict[cell].append((x, y))
                continue  # 여기서 BFS 진행을 멈추고 다음 위치로 넘어감

        #  3. 다음 이동할 수 있는 곳 큐에 추가
        for dx, dy in directions:
            nx, ny = x + dx, y + dy
            if 0 <= nx < h and 0 <= ny < w and not visited[nx][ny] and building[nx][ny] != '*':
                add_to_queue(nx, ny)

    return doc_count

t = int(input().strip())  # 테스트 케이스 개수
for _ in range(t):
    h, w = map(int, input().split())
    building = [list(input().strip()) for _ in range(h)]
    keys = input().strip()

    if keys == "0":  # 처음에 가진 열쇠가 없으면 빈 리스트
        keys = []

    print(bfs(h, w, building, keys))

굉장히 길지만 그렇게 복잡하거나 어렵진 않은? 문제였으나

열쇠를 발견했을 때 어떻게 왔던길을 돌아 해당 문을 찾아갈지 떠올리지 못해 풀지 못했다...

[체크 포인트]

1. 가장자리에서 벽이 아닌 경우 빼고 모두 갈 수 있으니 큐에 넣어야 한다!

2. 그리고 문자열도

'a' <= cell <= 'z'

이런 식으로 조건문을 줄 수 있는 줄 몰랐다...ㅠㅠ

3. 열쇠 리스트는 셋으로 변경해서 중복을 방지한다!

4. 대문자 문과 위치를 저장하는 딕셔너리를 만드는게 중요하다!

door_dict = {chr(i): [] for i in range(ord('A'), ord('Z') + 1)}  # 대문자 문과 위치 저장

ord를 이용해 숫자로 바꿔 range에 넣어주고, key는 다시 chr을 이용해 대문자 문자열으로 이용한다! value는 리스트로 줘서 해당하는 문의 위치를 모두 저장한다!

그래서 키를 발견했을 경우 큐에 전부 집어넣고 비운다.

5. 문을 발견했는데 열쇠가 없을 경우 continue (다음 이동할 곳 큐에 추가하는 부분 실행 안되도록)

6. 방문확인 및 처리하고 큐에 추가하는 부분은 자주 쓰이는 반복적인 코드니까 아예 함수로 만들어놓는 것도 방법!