[백준 9328] 열쇠 (파이썬 / Python)

---

📑 문제

문제링크 : 열쇠

---

🤔 생각의 흐름

visited 리스트에 키 상태를 저장해가며 DFS 를 진행하려고 했습니다. 키 상태는 비트마스크를 이용하여, 이전에 방문했던 칸에 다시 도착하더라도 visited 에 저장되어 있는 키 상태와 다르다면 스택에 집어넣는 방식으로 구현하려고 했습니다.

그런데 풀다보니 코드도 복잡해지고 예외처리도 귀찮아지며, 왔던 칸을 다시 방문해야하는 일이 빈번히 일어난다면 느릴 것 같았습니다.

그래서 visited 는 boolean 으로 방문여부를 저장하도록 바꾸었습니다. ‘A’ ~ ‘Z’ 가 인덱스 0 ~ 25 에 매칭되는 stuck 리스트를 만들어줍니다. 문에 도착했을 때 해당 문을 열 수 있는 열쇠가 없다면 stuck 리스트에 문의 위치를 저장하고, 열쇠가 있다면 BFS(DFS) 를 진행해주는 큐(스택)에 문의 위치를 넣어줍니다.

---

🎯 풀이방법

구현, BFS, DFS 문제이며, 시간복잡도는 $O(h w)$ 입니다.

arr : 지도

adj(pos) : pos 의 상하좌우를 반환해주는 제너레이터

entrance() : 벽이 아닌 가장자리의 위치를 반환해주는 제너레이터

visit(pos) : 위치 pos 에 도착했을 때 visited 에 기록하고, pos 에 있는 문자에 따라 적절한 행동을 해주는 함수.

• . or $ : 다음 BFS(DFS) 에 탐색할 수 있도록 pos 를 큐(스택)에 넣어준다.
• a ~ z : 열쇠 k를 얻었다고 하면, key[k] = True 를 해주고, stuck[K] 에 저장된 위치들을 큐(스택)에 넣어준다. 그리고 pos 를 큐에 넣어준다.
• A ~ Z : 문 K라고 하면 key[k] == True 인지 확인하여, True 일 경우 pos 를 큐(스택)에 넣어주고, False 라면 pos 를 stuck[K] 에 넣어준다.
• * : 벽은 아무것도 해주지 않습니다.

key : ‘a’를 0, ‘z’를 25 에 매칭시켜 가지고 있는 키를 boolean 으로 기록하는 리스트

stuck : 열쇠가 없어 나아가지 못하는 문의 위치가 저장되어있는 2차원 리스트

1. 지도와 열쇠를 입력받고, 열쇠가 있다면 key 리스트에 해당 열쇠를 True 로 만들어줍니다.

2. 벽이 아닌 가장자리에서 시작하여 BFS(DFS) 를 진행합니다. 해당 입구에 방문한 적이 없다면 입구의 문자에 따라 적절한 행동(visit 함수)을 취한 뒤, 큐(스택)에 넣고 BFS(DFS) 를 시작합니다. 방문한적 있다면 다음 입구에서 2번 단계를 수행합니다.

3. 큐(스택)에서 원소를 꺼내어 해당 위치에 문서가 있다면 ans + 1 을 해줍니다. 그리고 상하좌우 이동할 수 있는 위치에 대해 적절한 행동(visit 함수)을 취해줍니다.

4. 벽이 아닌 모든 가장자리부터 2 ~ 3 번 단계를 수행하였다면 ans 를 출력해줍니다.

---

🔎 유의할 점

• 입구에 있는 것도 올바르게 처리해주어야 합니다. 제가 입구에 있는 문자를 처리해주지 않아서 계속 틀렸습니다…

---

💻 코드

from sys import stdin

input = stdin.readline


def solve():
    def adj(pos):
        r, c = pos // w, pos % w
        if 0 < r:
            yield pos - w
        if r < h - 1:
            yield pos + w
        if 0 < c:
            yield pos - 1
        if c < w - 1:
            yield pos + 1

    def entrance():
        for i in range(w):
            if arr[i] != '*':
                yield i

        idx = w
        for i in range(h - 2):
            if arr[idx] != '*':
                yield idx
            idx += w - 1
            if arr[idx] != '*':
                yield idx
            idx += 1

        for i in range(idx, _len):
            if arr[i] != '*':
                yield i

    # $: 36 / .: 46 / A: 65 / Z: 90 / a: 97 / z: 122
    def visit(pos):
        _pos = ord(arr[pos])
        # 빈 공간 or 문서
        if _pos <= 46:
            que.append(pos)
            visited[pos] = True
        # 문
        elif _pos <= 90:
            d = _pos - 65
            if key[d]:
                que.append(pos)
            else:
                stuck[d].append(pos)

            visited[pos] = True
        # 열쇠
        else:
            k = _pos - 97
            if not key[k]:
                key[k] = True
                que.extend(stuck[k])
            que.append(pos)
            visited[pos] = True

    for _ in range(int(input())):
        h, w = map(int, input().split())
        _len = h * w
        arr = ''

        for _ in range(h):
            arr += input()[:-1]

        key_str = input()[:-1]
        key = [False] * 26
        if key_str != '0':
            for k in key_str:
                key[ord(k) - 97] = True

        stuck = [[] for _ in range(26)]
        visited = [False] * _len

        ans = 0
        # entrance() 에서 가능한 입구만 yield 해준다
        for e in entrance():
            if not visited[e]:
                que = []
                visit(e)
                while que:
                    pos = que.pop()
                    # 문서인 경우
                    if arr[pos] == '$':
                        ans += 1
                    for nxt in adj(pos):
                        if arr[nxt] != '*' and not visited[nxt]:
                            visit(nxt)

        print(ans)


if __name__ == '__main__':
    solve()