[백준 - Python] 1194 - 달이 차오른다, 가자

0.  문제 링크

 

 

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

1194번: 달이 차오른다, 가자.

---

1.  풀이 방법

 

 

1. BFS 문제이고, 방문 표시를 잘해야 한다.
2. 특정 키를 가지고 있음을 비트로 표현하는데, 방문 표시는 특정 키들을 가지고 이 칸에 방문한 적이 있느냐? 가 되겠다.
3. 따라서 키는 총 6개이므로, 000 000 ~ 111 111의 경우의 수를 가질 수 있다. 따라서 총 64개의 경우의 수가 존재한다.
4. 이제부터 모든 칸을 돌면서 특정 비트(특정 키를 가지고 방문했는지)를 체크하면서 방문하면 되겠다.
5. 결론적으로 visited[n][m][64]로 방문 표시하면 되겠다.
6. 만약 가지고 있는 키 = myKey를 가지고, 방문했는데 visited[n][m][myKey]에 방문한 적이 없다면 방문하고 방문 표시를 하면 된다.

---

2.  코드

 

 

import sys
from collections import deque
input = sys.stdin.readline


def bfs(dq):
    dist = -1
    while dq:
        dist += 1
        for _ in range(len(dq)):
            y, x, keys = dq.popleft()
            for dy, dx in dir:
                ny, nx = y + dy, x + dx
                if 0 <= ny < n and 0 <= nx < m and check[ny][nx][keys]:
                    match maps[ny][nx]:     # 구별함
                        case '#': continue

                        case '.': 
                            check[ny][nx][keys] = False
                            dq.append((ny, nx, keys))

                        case '1':
                            return dist + 1

                        case _:
                            if (k := maps[ny][nx]) in key:      # 키의 자리라면
                                newKeys = keys | key[k]     # or 연산을 통해 키를 획득함 -> 가지고 있어도 상관없음
                                if check[ny][nx][newKeys]:      # 방문한 전적이 있다면 패스
                                    check[ny][nx][newKeys] = False
                                    dq.append((ny, nx, newKeys))

                            elif (d := maps[ny][nx]) in door:       # 문이라면
                                if door[d] & keys:      # 그리고 키를 가지고 있다면
                                    check[ny][nx][keys] = False
                                    dq.append((ny, nx, keys))

    return -1


if __name__ == "__main__":
    n, m = map(int, input().split())
    maps = [list(input().rstrip()) for _ in range(n)]
    check = [[[True] * 2**6 for _ in range(m)] for _ in range(n)]
    dq = deque()
    dir = [(1, 0), (-1, 0), (0, 1), (0, -1)]
    key = {'a' : 1, 'b' : 2, 'c' : 4, 'd' : 8, 'e' : 16, 'f' : 32}
    door = {'A' : 1, 'B' : 2, 'C' : 4, 'D' : 8, 'E' : 16, 'F' : 32}

    for y in range(n):
        for x in range(m):
            if maps[y][x] == '0':
                dq.append((y, x, 0))
                check[y][x][0] = False
                maps[y][x] = '.'
                break
        else:
            continue
        break

    print(bfs(dq))

---

3.  마무리