[백준] 움직이는 미로 탈출

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

16954번: 움직이는 미로 탈출

라운드 방식으로 진행하는 BFS로 풀이하였습니다. 욱제가 각 라운드마다 움직일 수 있는 모든 위치를 BFS를 통해 저장해둡니다. 그 다음 위치를 저장해둔 벽의 위치를 라운드마다 한칸씩 밑으로 내려주면 됩니다. 만약 BFS를 통해 오른쪽 끝 위치에 도달할 수 있다면 탈출이 가능합니다.

 

이 문제의 포인트는 2가지입니다. 욱제가 제자리에 계속 있을 수 있다는 점, 벽을 움직일  때 행이 더 큰 벽부터 움직여야하나는 점입니다. 만약 같은 열에 위아래로 벽이 있는 경우 잘못하면 벽의 위치를 갱신하는 과정에서 실수로 벽을 지울 수 있기 때문입니다.

 

import sys
from collections import deque

#sys.stdin = open("input.txt", "r")
input = sys.stdin.readline

n = 8

board = [
    list(map(str, input().rstrip()))
    for _ in range(n)
]

walls = deque([])

# 벽의 위치를 저장한다.
for i in range(n - 1, -1, -1):
    for j in range(n):
        if board[i][j] == '#':
            walls.append((i, j))

dys = [-1, -1, -1, 0, 0, 1, 1, 1, 0]
dxs = [-1, 0, 1, -1, 1, -1, 0, 1, 0]

q = deque([(n - 1, 0)])
visited = [
    [False] * n
    for _ in range(n)
]

def inRange(y, x):
    return 0 <= y < n and 0 <= x < n

def bfs():
    visited = [
        [False] * n
        for _ in range(n)
    ]

    size = len(q)

    # 한 라운드를 진행한다.
    for _ in range(size):
        y, x = q.popleft()

        if y == 0 and x == n - 1:
            return True
        # 현재 위치에 벽이 내려온 경우
        if board[y][x] == '#':
            continue

        for dy, dx, in zip(dys, dxs):
            ny = y + dy
            nx = x + dx

            if inRange(ny, nx) and not visited[ny][nx] and board[ny][nx] != '#':
                q.append((ny, nx))
                visited[ny][nx] = True

    return False

while q:
    # 한칸을 움직인다.
    if bfs():
        print(1)
        sys.exit(0)

    size = len(walls)
    # 벽을 움직인다.
    for i in range(size):
        wall = walls.popleft()
        y, x = wall
        # 현재 위치를 빈공간으로 만들어 준다.
        board[y][x] = '.'

        if inRange(y + 1, x):
            walls.append((y + 1, x))
            board[y + 1][x] = '#'


print(0)