[백준 1194] 달이 차오른다, 가자. (파이썬 / Python)

---

📑 문제

문제링크 : 달이 차오른다, 가자.

---

🎯 풀이방법

BFS 문제입니다.

arr : 1차원 리스트로 저장된 미로

start : 시작지점

adj(pos) : pos에서 갈 수 있는(벽이 아닌) 다음위치를 반환해주는 제너레이터

visited[i][j] : i번 위치에 열쇠상태 j로(비트마스킹) 방문한적 있는지 여부

1. 출발 지점이 어디인지 파악합니다.

2. 출발 지점으로부터 상하좌우로 벽이 아닌 칸이라면 이동합니다.

3. 이동한 칸이 어떤 칸인지에 따라 해야할 행동이 나뉩니다.

   1. 열쇠: 알파벳에 맞게 가지고 있는 키를 비트마스킹 해줍니다. 예를 들어 ‘a’는 0번째이므로 1 « 0, ‘d’는 3번째이므로 1 « 3 으로 비트마스킹 해줍니다.

   2. 문: 가지고 있는 열쇠 중 해당 열쇠가 있는지 확인합니다. 만약 가지고 있지 않다면 큐에 해당 칸을 넣어주지 않습니다.

   3. 출구: 출구라면 현재 BFS 단계를 return 해줍니다.

   4. ‘0’: 출발지점이라면 특별히 해줄 행동은 없습니다.

4. 3번을 수행하고 해당 칸에 존재할 수 있으며, 현재의 key 상태로 해당칸에 방문한 적이 없다면 que에 넣어줍니다.

5. que가 빌 때까지 계속해서 BFS를 진행합니다. 만약 que가 비게 되면 탈출할 수 없으므로 -1을 return 해줍니다.

---

🔎 유의할 점

• 단순히 방문한 칸에 대해서만 DP를 하면 안됩니다. 가지고 있는 key에 대해서도 고려하여 각 칸의 방문여부를 체크해야 합니다.

---

💻 코드

from sys import stdin

input = stdin.readline


def solve():
    N, M = map(int, input().split())
    _len = N * M
    arr = [0] * _len
    for i in range(N):
        idx = i * M
        arr[idx:idx+M] = input()[:-1]

    start = arr.index('0')

    def adj(pos):
        r, c = pos // M, pos % M
        if 0 < r and arr[pos-M] != '#':
            yield pos-M
        if r < N - 1 and arr[pos+M] != '#':
            yield pos+M
        if 0 < c and arr[pos-1] != '#':
            yield pos-1
        if c < M - 1 and arr[pos+1] != '#':
            yield pos+1

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

    # (pos, key)
    que = [(start, 0)]
    visited[start][0] = True

    ans = 1
    while que:
        new_que = []
        for pos, org_key in que:
            for nxt in adj(pos):
                cell = ord(arr[nxt])
                key = org_key

                # 문인 경우
                if 65 <= cell <= 70:
                    # 해당하는 열쇠가 없는 경우
                    if not key & (1 << (cell - 65)):
                        continue

                # 키인 경우
                elif 97 <= cell <= 102:
                    key |= 1 << (cell - 97)

                # '1'인 경우
                elif cell == 49:
                    return ans

                if not visited[nxt][key]:
                    visited[nxt][key] = True
                    new_que.append((nxt, key))

        que = new_que
        ans += 1

    return -1


if __name__ == '__main__':
    print(solve())