16954: 움직이는 미로 탈출

• 일반적인 bfs 문제처럼 queue가 빌 때까지 while문을 도는데, 이 문제에선 한 번의 turn마다 이동할 수 있는 경우를 한번에 처리해주어야 한다
  -> 현재 queue에 있는 노드의 개수만큼 for문을 돌면서 조건에 맞는 경우에 9가지 방향(현재 위치에 서있는 경우 포함)으로 움직여준다
• 한 번의 turn이 끝난 후, 벽이 아래로 한 칸 이동해야하는데 그냥 pop() + appendleft() 연산으로 간편하게 이동시킬 수 있음
• turn이 진행될 때마다 turn의 개수를 세주어 turn이 9가 됐을 때는 board에 남아있는 벽이 없기 때문에 True를 return 해줌
• turn마다 visit 리스트를 이용해 중복되는 노드를 방문하지 않도록 하여 시간을 단축시킴

import sys
from collections import deque

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

def bfs():
    queue = deque()
    queue.append([7, 0])

    turn = 0
    while queue:
        visit = [[False] * 8 for _ in range(8)] #중복 제거 및 시간 단축을 위함
        for _ in range(len(queue)): #한번의 turn
            x, y = queue.popleft()
            if x == 0 and y == 7: #도착
                return True
            if board[x][y] == '.': #벽에 갇히지 않은 경우에 이동 가능
                for i in range(9):
                    nx = x + dx[i]; ny = y + dy[i]
                    if 0 <= nx < 8 and 0 <= ny < 8:
                        if board[nx][ny] == '.' and not visit[nx][ny]:
                            queue.append([nx, ny])
                            visit[nx][ny] = True

        board.pop()
        board.appendleft(['.', '.', '.', '.', '.', '.', '.', '.'])
        turn += 1
        if turn == 9:
            return True

    return False

board = deque([])
for _ in range(8):
    board.append(list(sys.stdin.readline()[:-1]))

if bfs():
    print(1)
else:
    print(0)