이번 문제는 BFS를 통해 해결하였다. 벽의 좌표를 리스트로 입력받고, BFS를 통해 움직이는 것을 구현하였다. 이때 벽이 움직이는 시점을 깔끔하게 하기 위해 q 안에 있는 모든 원소들을 순회하며 q를 popleft() 시켰다. 여기서 꺼낸 값들을 주어진 9가지 방향으로 이동시키고, 방문처리를 하였다. 이 과정이 끝나면 벽을 움직이도록 하였다. 그리고 제자리 이동의 경우, 방문처리가 되어 버리면 하지 못하기 때문에, 벽이 존재하는 한, while문의 매 반복마다 방문처리 리스트를 새로 갱신해주어 방문할 수 있도록 하게 하였다.

Code

from collections import deque
grid = [list(str(input())) for _ in range(8)]
wy, wx = 7, 0
ey, ex = 0, 7
dy, dx = [0, -1, -1, 0, 1, 1, 1, 0, -1], [0, 0, 1, 1, 1, 0, -1, -1, -1]
walls = []
for i in range(8):
    for j in range(8):
        if grid[i][j] == '#':
            walls.append((i, j))
def drop_walls():
    global walls
    new_walls = []
    for y, x in walls:
        if y < 7:
            new_walls.append((y+1, x))
    walls = new_walls[:]
def bfs():
    q = deque()
    q.append((7, 0))
    visited = [[False for _ in range(8)] for _ in range(8)]
    while q:
        for _ in range(len(q)):
            y, x = q.popleft()
            if (y, x) in set(walls):
                continue
            if (y, x) == (ey, ex):
                return True
            for i in range(9):
                ny, nx = y+dy[i], x+dx[i]
                if 0 <= ny < 8 and 0 <= nx < 8 and not visited[ny][nx] and (ny, nx) not in set(walls):
                    visited[ny][nx] = True
                    q.append((ny, nx))
        if walls:
            visited = [[False for _ in range(8)] for _ in range(8)]
        drop_walls()
if bfs():
    print(1)
else:
    print(0)