[BOJ/python] 9328번 열쇠

 

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

9328번: 열쇠

문제 해석

 

외부와의 출입이 자유로운 빌딩에서 훔칠 수 있는 문서($)의 갯수를 출력하는 문제이다.

이때 소문자 알파벳은 열쇠이고, 대문자 알파벳은 문이다. 열쇠가 존재하면 해당 열쇠의 문을 열어 지나갈 수 있다.

---

코드

 

# BOJ 9328

# 로직
# 먼저 시작 외부와 연결된 곳 즉 시작 위치가 될 수 있는 지점들은 startDir에 저장
# 열쇠의 종류를 입력받고, ord를 사용해 key 배열에 열쇠의 유무를 저장
# 이때 열쇠가 없는 0을 입력받은 상황 빠짐없이 예외처리
# bfs를 돌리는데 시작시, startDir배열의 모든 값을 큐에 넣고 bfs
# startDir의 좌표가 . 일때, $일때 열쇠일때, 문일때 모두 예외처리하여 큐에 집어 넣음
# while문 안에서도 해당 좌표가 좌표가 . 일때, $일때 열쇠일때, 문일때에 따라 모두 예외처리 하는데
# 열쇠일때는 큐를 clear하고, 시작 위치의 좌표를 다시 큐에 넣어주어 bfs를 돌려주었음.
# 따라서 열쇠를 획득하고, 들어가지 못하는 문들에 대한 탐색이 다시 이루어져 모든 경우 탐색이 가능함.


from collections import deque

t = int(input())

for ttt in range(t):
    n, m = map(int, input().split())
    dx, dy = [-1, 1, 0, 0], [0, 0, -1, 1] # 상 하 좌 우
    arr = []
    startDir = []
    visit = [[0] * m for _ in range(n)]

    # Input, startDir에 시작위치 좌표 저장
    for i in range(n):
        temp = list(input())
        for j in range(m):
            if i == 0 or j == 0 or i == n - 1 or j == m - 1: # 끝점일 때
                # 열쇠, 길, 문 모두 시작 위치가 될 수 있음.
                if temp[j] == '.' or (ord('a') <= ord(temp[j]) <= ord('z')): startDir.append((i, j))
                if ord('A') <= ord(temp[j]) <= ord('Z'): startDir.append((i, j))
                if temp[j] == '$': startDir.append((i, j))
        arr.append(temp)

    # 열쇠 정보 저장
    # 열쇠 정보는 ord를 통해 list로 관리
    key = [0] * 30
    keylist = list(input())
    if keylist[0] != '0': # 열쇠가 존재하지 않을 때 예외처리
        for k in keylist:
            key[ord(k) - ord('a')] = 1

    def bfs(visit):
        global ans
        q = deque()
        # 시작 가능한 위치 좌표를 모두 큐에 넣어줌.
        for i, j in startDir:
            # 길인 경우 무조건 가능
            if arr[i][j] == '.':
                q.append((i, j))
                visit[i][j] = 1
            # 열쇠인 경우 해당 열쇠를 획득하고, 큐에 넣어줌.
            elif ord('a') <= ord(arr[i][j]) <= ord('z'):
                q.append((i, j))
                key[ord(arr[i][j]) - ord('a')] = 1
                arr[i][j] = '.'
                visit[i][j] = 1
            # 문인 경우 해당 문에 대한 열쇠가 있는 경우에만 큐에 넣어줌.
            elif ord('A') <= ord(arr[i][j]) <= ord('Z'):
                if key[ord(arr[i][j]) - ord('A')] == 1:
                    arr[i][j] = '.'
                    q.append((i, j))
                    visit[i][j] = 1
            # 문서의 경우 문서를 획득하고(ans += 1), 큐에 넣어줌.
            elif arr[i][j] == '$':
                q.append((i, j))
                visit[i][j] = 1
                ans += 1
                arr[i][j] = '.'

        while q:
            i, j = q.popleft()
            for k in range(4):
                x, y = i + dx[k], j + dy[k]
                if not(0 <= x < n and 0 <= y < m): continue
                if visit[x][y] == 1: continue
                
                # 문서의 경우 획득하고, 큐에 넣어줌.
                if arr[x][y] == '$':
                    q.append((x, y))
                    visit[x][y] = 1
                    arr[x][y] = '.'
                    ans += 1
                # 길의 경우 큐에 넣어줌.
                elif arr[x][y] == '.':
                    q.append((x, y))
                    visit[x][y] = 1

                # 열쇠의 경우 
                elif ord('a') <= ord(arr[x][y]) <= ord('z'):
                    # 해당 열쇠를 얻은 상태면 그냥 큐에 넣어줌
                    if key[ord(arr[x][y]) - ord('a')] == 1:
                        q.append((x, y))
                        arr[x][y] = '.'
                        visit[x][y] = 1
                    # 처음 열쇠를 획득하면, 열쇠를 얻었다고 key 배열의 값을 변경한 뒤
                    # 큐와 visit을 clear하고, 시작 위치의 값을 큐에 넣어 다시 bfs 탐색
                    else:
                        key[ord(arr[x][y]) - ord('a')] = 1
                        arr[x][y] = '.'
                        q.clear()
                        visit = [[0] * m for _ in range(n)]
                        # 시작 위치의 배열의 종류에 따라 처리
                        for i, j in startDir:
                            if arr[i][j] == '.':
                                q.append((i, j))
                                visit[i][j] = 1
                            elif ord('a') <= ord(arr[i][j]) <= ord('z'):
                                q.append((i, j))
                                key[ord(arr[i][j]) - ord('a')] = 1
                                arr[i][j] = '.'
                                visit[i][j] = 1
                            elif ord('A') <= ord(arr[i][j]) <= ord('Z'):
                                if key[ord(arr[i][j]) - ord('A')] == 1:
                                    arr[i][j] = '.'
                                    q.append((i, j))
                                    visit[i][j] = 1
                # 문의 경우 해당 문을 열 수 있으면 큐에 넣음.
                elif ord('A') <= ord(arr[x][y]) <= ord('Z'):
                    if key[ord(arr[x][y]) - ord('A')] == 1:
                        arr[x][y] = '.'
                        q.append((x, y))
                        visit[x][y] = 1

    ans = 0
    bfs(visit)
    print(ans)

---

문제 풀이

 

주석 참고.

 

나는 열쇠를 얻으면 그동안 못지나갔던 문을 지나가기 위해 큐를 모두 지운뒤 시작위치가 되는 startDir 배열에 존재하는 좌표를 큐에 다시 넣고 방문 노드를 초기화 한 뒤 재탐색 하도록 구현했다. 하지만 다른 답안을 보니 열쇠를 얻을 경우 방문 노드를 초기화 하고, 열쇠를 통해 열 수 있는 문의 좌표를 큐에 넣어주도록 하였다.

 

근데 내 생각엔 해당 방식으로 구현하면 애초에 해당문에 도달할 수 없는 상황에도 bfs 큐에 들어가여 탐색 하기 때문에 문제가 되지 않을까 싶은데.. (밑의 테이블 처럼..)

*	*	*	*	*
*	A	*	$	.
*	$	*	a	*
*	*	*	*	*