[파이썬/Python] 백준 9328번: 열쇠

📌 문제 : 백준 9328번

---

📌 문제 탐색하기

h : 지도 높이 ($2 ≤ h ≤ 100$)
w : 지도 너비 ($2 ≤ w ≤ 100$)

문제 풀이

h×w의 지도 정보를 통해 문서의 위치를 확인하고 열쇠를 찾아 문을 열어 훔칠 수 있는 문서의 최대 개수를 구하는 문제이다.

🗺️ 지도 정보

• h개 줄에는 빌딩을 나타내는 w개의 문자
  • . : 빈 공간
  • * : 벽 (통과 ❌)
  • $ : 훔쳐야하는 문서 위치
  • 알파벳 대문자 : 문 (모든 문은 잠긴 상태)
    • 열 수 있는 열쇠 여러 개일 수 있음
  • 알파벳 소문자 : 문의 열쇠 (열쇠 하나도 없으면 0 입력)
    • 열쇠 여러 번 사용 ⭕️
• 가능한 이동 방향 → 상하좌우
• 위치
  • 처음에 빌딩 밖 위치
  • 가장자리의 벽이 아닌 곳을 통해 빌딩 안팎 이동 가능

→ BFS를 활용한다!!

지도 확인

• 가장자리의 벽이 아닌 곳으로 진입 가능
  • 입력된 지도를 둘러싼 빈 공간이 있음을 표현
  • 지도 입력 시 .를 추가해 리스트에 저장
• 새로 만들어진 지도와 동일한 크기의 방문리스트 정의

BFS

• 4가지 방향 탐색
  • 범위 내이면서 벽이 아니고 방문하지 않은 칸 확인
• 4가지 경우 고려
  • 빈 공간
    • 방문 처리
    • bfs 이어가기
  • 문서 발견
    • 훔친 문서 개수 증가
    • 방문 처리
    • 빈 공간으로 변경
    • bfs 이어가기
  • 문 발견
    • 키 있다면 지나가기 + 빈 공간 변경 + 방문 처리 + 계속 이동 + 빈 공간으로 변경
  • 키 발견
    • 없는 키라면 리스트에 추가 + 계속 이동 + 방문리스트 초기화해 새로 탐색 + 방문 처리 + 계속 이동 + 빈 공간으로 변경

가능한 시간복잡도

bfs 수행 → $O(h*w)$
키 발견 시 bfs 다시 수행 → $O(keys * h*w)$

최종 시간복잡도
$O(keys * h*w)$으로 최악의 경우 키의 수는 대문자+소문자 수이므로 $O(26 * 10^4)이 되어 1초 내에 수행할 수 있을 것이다.

알고리즘 선택

bfs 수행 반복

---

📌 코드 설계하기

1. bfs 수행
2. N, M 입력
3. 치즈 정보 입력
4. 4면 접근 방향
5. 시간 초기화
6. 치즈가 다 없어질 때까지 bfs 반복

---

📌 시도 회차 수정 사항

1회차

• 시간초과가 나왔다.
• 확인해보니 키를 발견했을 때 이미 가지고 있는 경우, 아닌 경우를 따지지 않고 수행하다보니 방문리스트도 계속 초기화되면서 시간이 오래 걸리는 문제가 발생한 것 같다.

2회차

• 얻은 적 없는 문서가 있는 칸에 도착했을 때 원하는 일들을 모두 수행하고 마저 탐색을 이어가도록 queue에 좌표를 넣어줘야하는데 그것을 빼먹어서 틀렸다.

---

📌 정답 코드

import sys
from collections import deque

input = sys.stdin.readline

# 4가지 이동 방향
moves = [(-1, 0), (1, 0), (0, -1), (0, 1)]


# bfs 함수 정의
def bfs():
    # 방문 리스트 정의
    visited = [[0] * (w + 2) for _ in range(h + 2)]

    # 훔칠 수 있는 문서 개수 저장 변수 정의
    count = 0

    # 큐 정의
    queue = deque([(0, 0)])
    # 방문 처리
    visited[0][0] = 1

    # 큐 빌 때까지 수행
    while queue:
        x, y = queue.popleft()
        visited[x][y] = 1

        # 4가지 방향 확인
        for i in range(4):
            nx, ny = x + moves[i][0], y + moves[i][1]

            # 범위 내이고 벽이 아니면서 방문한 적 없는 곳이라면 이동
            if 0 <= nx < h+2 and 0 <= ny < w+2 and map_info[nx][ny] != "*" and not visited[nx][ny]:
                # 빈 공간이면 계속 이동
                if map_info[nx][ny] == ".":
                    queue.append((nx, ny))
                    visited[nx][ny] = 1

                # 문서라면 개수 세기
                elif map_info[nx][ny] == "$":
                    # 찾은 문서 개수 증가
                    count += 1
                    # 방문 처리
                    visited[nx][ny] = 1
                    # 빈공간으로 변경
                    map_info[nx][ny] = "."
                    # 계속 이동
                    queue.append((nx, ny))

                # 문 발견
                elif "A" <= map_info[nx][ny] <= "Z":
                    # 키가 있다면 지나가기
                    if map_info[nx][ny].lower() in keys:
                        # 빈 공간 변경
                        map_info[nx][ny] = "."
                        # 방문 처리
                        visited[nx][ny] = 1
                        # 계속 이동
                        queue.append((nx, ny))

                # 키 발견
                elif "a" <= map_info[nx][ny] <= "z":
                    # 없는 키라면
                    if map_info[nx][ny] not in keys:
                        # 가지고 있는 키 리스트에 추가
                        keys.append(map_info[nx][ny])
                        # 계속 이동
                        queue.append((nx, ny))
                        # 방문리스트 초기화해 새로 탐색
                        visited = [[0] * (w + 2) for _ in range(h + 2)]

                    # 있는 키라면 방문 처리 후 지나가기
                    else:
                        # 계속 이동
                        queue.append((nx, ny))

                    # 빈 공간 변경
                    map_info[nx][ny] = "."
                    # 방문 처리
                    visited[nx][ny] = 1

    return count


# 테스트 케이스 수 입력
T = int(input())

# 정답 모두 저장할 리스트 정의
answer = []

# 테스트 케이스마다 반복
for _ in range(T):
    # h, w 입력
    h, w = map(int, input().split())

    # 빌딩 입력
    map_info = [['.'] * (w + 2)] + [["."] + list(map(str, input().rstrip())) + ["."] for _ in range(h)] + [['.'] * (w + 2)]

    # 가지고 있는 키 입력
    keys = list(map(str, input().rstrip()))

    # bfs 수행 후 결과 추가
    answer.append(bfs())

# 결과 출력
for a in answer:
    print(a)

• 결과