백준 16954 파이썬 - 움직이는 미로탈출

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

16954번: 움직이는 미로 탈출

문제

욱제는 학교 숙제로 크기가 8×8인 체스판에서 탈출하는 게임을 만들었다. 체스판의 모든 칸은 빈 칸 또는 벽 중 하나이다. 욱제의 캐릭터는 가장 왼쪽 아랫 칸에 있고, 이 캐릭터는 가장 오른쪽 윗 칸으로 이동해야 한다.

이 게임의 특징은 벽이 움직인다는 점이다. 1초마다 모든 벽이 아래에 있는 행으로 한 칸씩 내려가고, 가장 아래에 있어서 아래에 행이 없다면 벽이 사라지게 된다. 욱제의 캐릭터는 1초에 인접한 한 칸 또는 대각선 방향으로 인접한 한 칸으로 이동하거나, 현재 위치에 서 있을 수 있다. 이동할 때는 빈 칸으로만 이동할 수 있다.

1초 동안 욱제의 캐릭터가 먼저 이동하고, 그 다음 벽이 이동한다. 벽이 캐릭터가 있는 칸으로 이동하면 더 이상 캐릭터는 이동할 수 없다.

욱제의 캐릭터가 가장 오른쪽 윗 칸으로 이동할 수 있는지 없는지 구해보자.

코드

import sys
from collections import deque
board = [list(sys.stdin.readline().rstrip()) for _ in range(8)]
walls = [(i, j) for i in range(8) for j in range(8) if board[i][j] == '#']
dr = [[0, 0], [1, 0], [0, 1], [-1, 0], [0, -1], [1, 1], [1, -1], [-1, 1], [-1, -1]]
def bfs():
    q = deque()
    q.append((7, 0, 0))
    while q:
        x, y, time = q.popleft()
        for dx, dy in dr:
            nx = x + dx
            ny = y + dy
            if 0 <= nx < 8 and 0 <= ny < 8 and board[nx - time][ny] != '#' and board[nx - time - 1][ny] != '#':
                if nx - time < 0:
                    return 1
                q.append((nx, ny, time + 1))
    return 0
print(bfs())

풀이

움직이지 않는 것은 dr의 배열 0, 0으로 처리하고, time이라는 변수로 벽을 움직이는 것처럼 처리한다. 어차피 1만큼 밑으로 내려오므로 이렇게 처리하면 배열을 수정하거나 다른 연산을 하는 일이 줄어들 수 있다. 맨 윗줄에만 오면 어떻게든 맨 오른쪽 윗 칸에 갈 수 있으므로 맨 위에 오는 것만 체크하여 1 혹은 0 을 상황에 맞게 출력한다.