[Python] 백준 9328번: 열쇠

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

9328번: 열쇠

 

import sys
input = sys.stdin.readline

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


def setIsDoorAvailable(keys):
    if keys != "0":
        for c in keys:
            isDoorAvailable[convertAlphabetToNumber(c)] = True


def setAvailableDocumentCount():
    outerPositions = \
        [(0, j) for j in range(W)] + [(H-1, j) for j in range(W)] + \
        [(i, 0) for i in range(1, H-1)] + [(i, W-1) for i in range(1, H-1)]

    for x, y in outerPositions:
        if isPositionReachable((x, y)):
            searchForSector((x, y))


def searchForSector(pos):
    todo = [pos]

    while todo:
        x, y = todo.pop(0)

        if isVisited[x][y] == False:
            todo += searchAndGetNextPositions((x, y))


def searchAndGetNextPositions(pos):
    global availableDocumentCount

    todo = [pos]
    unlockedDoorIndices = []
    isVisited[pos[0]][pos[1]] = True

    while todo:
        x, y = todo.pop(0)
        c = buildingMap[x][y]
        cIndex = convertAlphabetToNumber(c)

        # 키를 얻음으로써 문을 개방함
        if 'a' <= c <= 'z':
            if isDoorAvailable[cIndex] == False:
                isDoorAvailable[cIndex] = True
                unlockedDoorIndices.append(cIndex)
        # 문서
        elif c == '$':
            availableDocumentCount += 1

        # 인접 노드 추가
        for i in range(4):
            nextX, nextY = x + dx[i], y + dy[i]

            if 0 <= nextX <= H-1 and 0 <= nextY <= W-1:
                if isPositionReachable((nextX, nextY)):
                    todo.append((nextX, nextY))
                    isVisited[nextX][nextY] = True

    # 이번 탐색으로 열린 문들 중에, 이전에 접근 실패했던 인접 좌표들을 반환함
    nextPositions = []
    for i in unlockedDoorIndices:
        for x, y in adjacentUnavailableDoorPositions[i]:
            nextPositions.append((x, y))

    return nextPositions


def convertAlphabetToNumber(c):
    if 'a' <= c <= 'z':
        return ord(c)-ord('a')
    elif 'A' <= c <= 'Z':
        return ord(c)-ord('A')
    else:
        return -1


def isPositionReachable(pos):
    x, y = pos
    c = buildingMap[x][y]
    cIndex = convertAlphabetToNumber(c)

    if (isVisited[x][y] == False) and (c == '.' or c == '$' or ('a' <= c <= 'z') or ('A' <= c <= 'Z' and isDoorAvailable[cIndex])):
        return True
    else:
        if 'A' <= c <= 'Z' and isDoorAvailable[cIndex] == False:
            adjacentUnavailableDoorPositions[cIndex].append((x, y))

        return False


if __name__ == '__main__':
    T = int(input())

    for _ in range(T):
        # 입력
        H, W = map(int, input().split())
        buildingMap = [str(input().rstrip()) for _ in range(H)]
        keys = str(input().rstrip())

        # 탐색을 위한 변수 초기화
        isDoorAvailable = [False]*26
        setIsDoorAvailable(keys)

        isVisited = [[False]*W for _ in range(H)]
        adjacentUnavailableDoorPositions = [[] for _ in range(26)]
        
        availableDocumentCount = 0

        # 탐색
        setAvailableDocumentCount()

        # 출력
        print(availableDocumentCount)

 

BFS로 진행한다. 우선 간단하게 진행 구조를 설명하자면 다음과 같다.

 - 외곽 라인을 돌면서, 접근 가능한 곳을 찾는다.

 - 해당 진입점에서 접근할 수 있는 모든 곳을 '섹터'라고 명한다. 해당 섹터의 진입점을 시작으로 탐색을 시작한다.

 - bfs 탐색을 진행한다. 여기서 키와 문서에 대한 처리를 모두 해준다. 탐색이 끝나면 다음에 bfs 탐색할 지점을 정해줄 것이다. 기준은, '이번 탐색을 통해 열 수 있게 된 문들 중에, 이전에 접근 시도하였다가 실패한 노드들'이다.

 

 

구체적인 설명에 앞서, 문제를 풀기 위해 쓰이는 변수들에 대해 설명한다.

 - isDoorAvailable: 이름 그대로다. isDoorAvailable[3] = True는, 문 D를 열 수 있다는 것을 나타낸다. setIsDoorAvailable() 함수로 초기화된다.

 - isVisited: (생략)

 - adjacentUnavailableDoorPositions: bfs를 진행하면서, 특정 노드들에 대해 방문이 가능한지 여부를 isPositionReachable() 함수를 통해 확인할 것이다. 이 때, 방문은 불가능하지만 문(A~Z)에 해당하는 좌표들을 이곳에 담을 것이다. 문의 좌표들을 기록해두었다가, 나중에 열쇠를 얻게되었을 때 해당 문들의 좌표를 탐색할 것이다.

 - availableDocumentCount: 출력할 값이다.

 

 

우선 탐색 함수의 진행 순서 및 설명은 다음과 같다.

 - setAvailableDocumentCount():

메인 함수다. 외곽 라인을 반복문으로 돌면서, 접근 가능할 경우(isPositionReachable())에 아래의 함수를 호출한다.

 

 - searchForSector():

한 섹터의 진입점부터 시작해서 탐색을 진행한다. 아래의 함수를 통해 다음에 탐색해야할 좌표를 얻어온다.

 

 - searchAndGetNextPositions():

가장 중요한 함수로, 한 지점에서 시작해서 bfs를 진행한다. 이 때, 방문한 곳이 키(a~z)일 경우, isDoorAvailable와 unlockedDoorIndices를 알맞게 설정해준다. unlockedDoorIndices의 쓰임에 대해선 후설하겠다. 방문한 곳이 문서($)일 경우 출력값인 availableDocumentCount를 증가시킨다. 다음으로, 인접 노드에 접근 가능할 경우 todo(BFS의 큐 역할)과 isVisited에 적당한 값을 넣어준다.

마지막으로, searchForSector()에서 다음에 탐색을 진행하게 될 nextPositions에 값을 넣어준다. 즉, 다음에 탐색해야할 곳을 정하는 부분이며, 이 함수를 통해 열쇠를 얻어서 열 수 있게 된 문들의 좌표들을 담아줄 것이다. 이전에 bfs 탐색에서, 키를 얻었을 때 unlockedDoorIndices에 알파벳의 인덱스값을 넣었다. 여기에 for문을 도는데, 또 adjacentUnavailableDoorPositions에 대해서 반복문을 돌면서 nextPositions에 추가할 것이다. adjacentUnavailableDoorPositions에는 isPositionReachable() 함수에서 해당 노드에 접근 가능한지 여부를 조사할 때 원소가 추가된다. isPositionReachable()을 통해 접근 시도를 했다는 것은, 접근 가능한 노드와 인접한다는 것을 의미한다. 즉, 키만 있으면 접근할 수 있다는 것이다. 만약 좌표를 이런 식으로 추가하지 않고, 탐색을 진행하기 전에 모든 문들의 좌표를 조사하게 된다면, 탐색으로 키를 얻음으로써 '지금 당장' 갈 수 있는 곳과 그렇지 못한 곳을 구분짓지 못하고 탐색을 시도하게 된다.

 

 

이 문제에서 가장 중요한 아이디어는, 접근을 시도했던 문들의 좌표를 저장하고, BFS를 통해 키를 얻었을 때 해당 좌표들에 대한 BFS 탐색을 진행한다는 것이다.

 

마지막으로 매우 중요한 반례를 하나 남긴다.

1

2 5

**B**

**$*b

 

푸는 게 정말 힘들었다.