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

www.acmicpc.net/problem/1194

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

 

문제풀이

N, M, board : 입력값

check : 특정 key를 가지고 방문 여부 체크

 

비트마스크를 이용한 BFS 문제였다. 평상시 비트마스크를 싫어하였는데 이 문제를 통해 조금은 친해(?)진 것 같다...

비트마스크를 활용한 풀이에 대한 설명은 아래 참고한 코드 URL 에 자세히 설명되어 있다.

 

1. '0' 부터 BFS 탐색

- 새롭게 이동할 곳이 '1' 이거나 '.' 이면 그냥 방문

- 새롭게 이동할 곳이 'a' ~ 'f' 사이 key가 존재하는 경우, 현재 key에서 or 연산을 통해 key 흭득하기

- 새롭게 이동할 곳이 'A' ~ 'F" 사이 door가 존재하는 경우, 현재 key에서 and 연산을 통해 문을 통과할 수 있는지 확인하기

 

2. '1'에 도달할 경우 거리(cnt) 리턴

- 도달하지 못할 경우 -1 리턴

 

코드

import sys
from collections import deque

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

def haveKey(cur_key, door):
    value = cur_key & (1 << (ord(door) - ord('A')))
    return True if value else False

def bfs(x, y):
    q = deque([(x, y, 0, 0)])
    check = [[[False] * (1 << 6) for _ in range(50)] for _ in range(50)]
    check[x][y][0] = True

    while q:
        x, y, cnt, key = q.popleft()
        if board[x][y] == '1': return cnt
        for k in range(4):
            nx, ny = x + dx[k], y + dy[k]
            if 0 <= nx < N and 0 <= ny < M:
                if not check[nx][ny][key]:
                    if board[nx][ny] == '1' or board[nx][ny] == '.':
                        check[nx][ny][key] = True
                        q.append((nx, ny, cnt + 1, key))
                    elif 'a' <= board[nx][ny] <= 'f':
                        tmp_key = key | (1 << (ord(board[nx][ny]) - ord('a')))
                        check[nx][ny][tmp_key] = True
                        q.append((nx, ny, cnt + 1, tmp_key))
                    elif 'A' <= board[nx][ny] <= 'Z':
                        if haveKey(key, board[nx][ny]):
                            check[nx][ny][key] = True
                            q.append((nx, ny, cnt + 1, key))
    return -1

if __name__ == '__main__':
    N, M = map(int, sys.stdin.readline().split())
    board = [list(map(str, sys.stdin.readline().rstrip())) for _ in range(N)]
    for i in range(N):
        for j in range(M):
            if board[i][j] == '0':
                sx, sy = i, j
                board[i][j] = '.'
    print(bfs(sx, sy))

 

결과

 

위 풀이는 'yabmoons' 님의 C++ 풀이를 참고한 코드입니다.

yabmoons.tistory.com/102

 

문제풀이나 코드에서 이상한 부분 지적은 언제나 환영합니다!