[Python] 9328 열쇠

[Gold I] 열쇠 - 9328 

[문제 링크](https://www.acmicpc.net/problem/9328)

---

💻 문제 정의

NxM 크기의 맵에서 빈 공간을 탐색하며 문서를 최대한 많이 훔치는 문제이다. 공간에는 벽, 문, 열쇠, 문서가 존재하고, 문과 열쇠는 알파벳으로 구성되어 있다. 소문자 알파벳(열쇠)을 가지고 있으면 대문자 알파벳(문)을 뚫고 지나갈 수 있게 된다.

획득할 수 있는 문서의 최대 개수를 구하는 프로그램을 작성하는 것이 목표이다.

💡 접근 및 설계

너비 우선 탐색을 이용하였다.

먼저 탐색을 시작할 지점을 선택해야 하는데, 문제의 예제를 보면 알 수 있듯이 시작점을 정의하기가 매우 애매하다. 또한 방문한 점을 기록하며 탐색을 이어나가자니 열쇠를 획득한 후 문을 열지 못했던 지점으로 돌아가는 방법이 없다는 문제가 있었다. 두 가지 핵심 문제를 해결하는 것을 목표로 접근하였다.

✏️ 알고리즘 풀이

matrix = []
matrix.append(["."] * (M+2))
for _ in range(N):
    matrix.append(["."] + list(input()) + ["."])
matrix.append(["."] * (M+2))

기존의 공간은 NxM 크기의 공간에 빈 공간, 벽, 문 등으로 구성되어 있었다. 이러한 공간에서 탐색을 시작할 단 하나의 점을 찾는 것은 매우 어렵다. 그렇기에 맵의 주변을 두르는 빈 공간을 추가해주었다. 따라서 우리는 (0, 0)에서 부터 탐색을 시작해도 큰 문제없이 탐색을 진행할 수 있게 된다.

key_input = input().strip()
keys = set() if key_input == "0" else set(key_input) # 현재 보유중인 열쇠 저장 셋 / "0"을 입력받으면 빈 셋
visited = [[False] * (M+2) for _ in range(N+2)] # 방문처리
dollar = [] # 서류 획득
door = defaultdict(list) # 문 앞에 대기중인 위치

핵심 자료구조 정의 부분이다.

keys : 처음에 주어진 열쇠 및 획득한 열쇠를 저장하는 셋(집합)

visited : 방문 처리를 위한 리스트

dollar : 획득한 서류의 좌표를 저장하는 리스트

door : 문을 만났을 때 해당 문을 통과하지 못한다면, 그 문의 좌표를 기억하는 리스트

dx = [0, 0, -1, 1]
dy = [1, -1, 0, 0]

def bfs(x, y):
    Q = deque()
    Q.append([x, y])
    visited[x][y] = True

    while Q:
        currX, currY = Q.popleft()

        for i in range(4):
            nextX = currX + dx[i]
            nextY = currY + dy[i]

            # 매트릭스 범위 안에 존재하고 벽이 아닐경우 전진
            if 0 <= nextX < N+2 and 0 <= nextY < M+2 and matrix[nextX][nextY] != "*" and not visited[nextX][nextY]:
                # 문을 만났을 때, 열쇠를 가지고 있다면
                if "A" <= matrix[nextX][nextY] <= "Z":
                    if matrix[nextX][nextY].lower() in keys:
                        # 해당 지점 방문 후 탐색 이어 나가기
                        visited[nextX][nextY] = True
                        Q.append([nextX, nextY])
                    
                    # 열쇠가 없어서 열지 못하다면 해당 지점 저장
                    else:
                        door[matrix[nextX][nextY].lower()].append([nextX, nextY])
                        continue

                # 열쇠라면 저장
                elif "a" <= matrix[nextX][nextY] <= "z":
                    key = matrix[nextX][nextY]
                    if key not in keys:
                        keys.add(key)

                        for x, y in door[key]:
                            visited[x][y] = True
                            Q.append([x, y])

                    door[key].clear()
                    visited[nextX][nextY] = True
                    Q.append([nextX, nextY])

                # 문서라면 훔치기
                elif matrix[nextX][nextY] == "$":
                    dollar.append([nextX, nextY])

                    visited[nextX][nextY] = True
                    Q.append([nextX, nextY])

                else:
                    visited[nextX][nextY] = True
                    Q.append([nextX, nextY])

탐색 알고리즘이다. 현재의 좌표를 기준으로 동, 서, 남, 북 네 방향으로 탐색을 진행한다.

방문하는 모든 점들은 정의된 공간 이내 존재하고, 벽이 아니며, 방문하지 않은 점들만 탐색한다.

만약 문을 만났다면, keys에 해당 문을 열 열쇠가 존재하는지 판별하고, 열쇠가 존재한다면 탐색을 이어나간다. 열쇠가 존재하지 않다면 door에 좌표를 추가한 후 다음 점 탐색으로 넘어간다.

만약 열쇠를 만났다면 keys안에 저장한다. 이미 획득한 열쇠라면 저장하지 않는다. 열쇠 획득과 동시에 해당 열쇠로 열 수 있는 문이 존재한다면 해당 문을 방문하고 해당 문에서부터 탐색을 이어나갈 수 있도록 Q에 저장한다. 열쇠로 문을 열고난 후, 해당 문은 door에서 제거한다. 이후 다음 탐색을 이어 나간다.

만약 문서를 만났다면 dollar에 해당 지점을 추가한다. 이후 다음 탐색을 이어 나간다.

위의 모든 조건이 아닌 경우(빈 공간인 경우) 다음 탐색을 이어 나간다.

🗒️ 최종 제출 코드

# 9328 열쇠

from collections import deque, defaultdict

dx = [0, 0, -1, 1]
dy = [1, -1, 0, 0]

def bfs(x, y):
    Q = deque()
    Q.append([x, y])
    visited[x][y] = True

    while Q:
        currX, currY = Q.popleft()

        for i in range(4):
            nextX = currX + dx[i]
            nextY = currY + dy[i]

            # 매트릭스 범위 안에 존재하고 벽이 아닐경우 전진
            if 0 <= nextX < N+2 and 0 <= nextY < M+2 and matrix[nextX][nextY] != "*" and not visited[nextX][nextY]:
                # 문을 만났을 때, 열쇠를 가지고 있다면
                if "A" <= matrix[nextX][nextY] <= "Z":
                    if matrix[nextX][nextY].lower() in keys:
                        # 해당 지점 방문 후 탐색 이어 나가기
                        visited[nextX][nextY] = True
                        Q.append([nextX, nextY])
                    
                    # 열쇠가 없어서 열지 못하다면 해당 지점 저장
                    else:
                        door[matrix[nextX][nextY].lower()].append([nextX, nextY])
                        continue

                # 열쇠라면 저장
                elif "a" <= matrix[nextX][nextY] <= "z":
                    key = matrix[nextX][nextY]
                    if key not in keys:
                        keys.add(key)

                        for x, y in door[key]:
                            visited[x][y] = True
                            Q.append([x, y])

                    door[key].clear()
                    visited[nextX][nextY] = True
                    Q.append([nextX, nextY])

                # 문서라면 훔치기
                elif matrix[nextX][nextY] == "$":
                    dollar.append([nextX, nextY])

                    visited[nextX][nextY] = True
                    Q.append([nextX, nextY])

                else:
                    visited[nextX][nextY] = True
                    Q.append([nextX, nextY])

T = int(input())

for _ in range(T):
    N, M = map(int, input().split())

    matrix = []
    matrix.append(["."] * (M+2))
    for _ in range(N):
        matrix.append(["."] + list(input()) + ["."])
    matrix.append(["."] * (M+2))

    key_input = input().strip()
    keys = set() if key_input == "0" else set(key_input) # 현재 보유중인 열쇠 저장 셋 / "0"을 입력받으면 빈 셋
    visited = [[False] * (M+2) for _ in range(N+2)] # 방문처리
    dollar = [] # 서류 획득
    door = defaultdict(list) # 문 앞에 대기중인 위치

    bfs(0, 0)

    print(len(dollar))

---

💭 오늘의 회고

꽤나 생각을 많이 요구했던 너비 우선 탐색 문제였다. 위의 풀이에도 나와 있듯이, 두 가지 핵심 문제를 풀기위해 많은 방법을 시도하였고, 시간도 오래 걸렸다. 특히나 주어진 공간 주위에 빈 공간을 두르는 방식은 정말 예상하지 못하였고, 구현을 하면서도 이게 맞나 생각이 들었다. 정말 아닐 것 같은 방법이었음에도 정답이 뜨는 것을 보고 참신한 풀이 방법이 많구나 생각이 들었다.