[python3] 백준 1194 풀이 ( "달이 차오른다, 가자." , BFS )

이번 문제는 오랜만에 그래프이다.

우선 문제를 읽어보면 몇가지 포인트가 존재한다.
1. 이동 횟수의 최솟값을 구한다. => BFS로 푼다.
2. 키가 있어야 문을 열수 있다. => 키를 찾고 왔던길을 다시 갈 수 있다. => visited를 키에 따라 따로 관리해야 한다. => 그럼 키에 따른 visited를 관리해야한다. 따라서 3차원으로 visited를 관리해야 한다.
* 이때 키는 bitmasking으로 관리해야 배열에 넣고 관리가 가능하다.

3차원으로 visited를 관리해야 하는 경우에는 [y][x][key]로 관리하여 key일때 y,x가 true 상태인지 false 상태인지 저장해준다. 사실 이러한 방식이 처음이라 이해가 어려웠다. 

만약 key가 3이고(000000000011 => a,b키를 가진경우) y와 x가 0,0 이라면 visited[0][0][3]이 true인지 false인지 확인하면 된다. 이렇게 키에 따른 visited를 관리하는 경우 BFS에서 가장 빠른 목적지에 도달 할 수 있는 장점이 존재한다...?

이러한 방식으로 코딩을 진행하면 생각보다 심플한 코드로 복잡한 로직을 해결할 수 있다.

from collections import deque


N, M = map(int, input().split())
board = [list(input()) for _ in range(N)]
for i in range(N):
    for j in range(M):
        if board[i][j] == '0':
            sy, sx = i, j
            board[i][j] = '.'


def BFS(y, x):
    dy = [0, 0, 1, -1]  # 동서남북
    dx = [1, -1, 0, 0]
    check = [[[False]*(1 << 6) for _ in range(50)] for _ in range(50)]
    check[y][x][0] = True  # 0은 키가 하나도 없다는것

    q = deque([[y, x, 0, 0]])
    while q:
        y, x, cnt, key = q.popleft()
        if board[y][x] == '1':
            return cnt
        for i in range(4):
            ny = y + dy[i]
            nx = x + dx[i]
            if 0 <= ny < N and 0 <= nx < M:
                if not check[ny][nx][key]:  # 가지 않은 경우
                    if board[ny][nx] == '1' or board[ny][nx] == '.':
                        check[ny][nx][key] = True
                        q.append([ny, nx, cnt+1, key])
                    elif 'a' <= board[ny][nx] <= 'f':  # 키를 만나는경우
                        check[ny][nx][key] = True
                        new = ord(board[ny][nx])-ord('a')
                        new = key | (1 << new)
                        q.append([ny, nx, cnt+1, new])
                    elif 'A' <= board[ny][nx] <= 'F':
                        if key & (1 << ord(board[ny][nx])-ord('A')):
                            check[ny][nx][key] = True
                            q.append([ny, nx, cnt+1, key])
    return -1


print(BFS(sy, sx))

 

비트 마스킹을 이용하여 flag를 배열 인덱스 처럼 활용가능하다. 상당히 유용하다. 일차원 배열을 정수로 핸들링 하기 때문에 복잡한 배열을 간단히 나타내는게 가능했다. 이전에는 비트마스킹으로 비교하는 것만 했는데 이러한 방식으로 사용가능 하다는 것을 배울 수 있었다.