[BOJ] 16954 움직이는 미로 탈출 (Python3)

문제

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

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

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

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

입력

8개 줄에 걸쳐서 체스판의 상태가 주어진다. ‘.’은 빈 칸, ‘#’는 벽이다. 가장 왼쪽 아랫칸은 항상 벽이 아니다.

출력

욱제의 캐릭터가 가장 오른쪽 윗 칸에 도착할 수 있으면 1, 없으면 0을 출력한다.

정답 코드

from collections import deque


def main():
    graph = []
    for i in range(8):
        graph.append(list(input()))
        
    graph = deque(graph)

    q = deque([(7, 0)])

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

    turn = 0
    while q:
        
        for i in range(len(q)):
            x, y = q.popleft()
            
            if graph[x][y] == '#':
                continue
                
            if x == 0 and y == 7:
                return 1

            for i in range(9):
                nx = x + dx[i]
                ny = y + dy[i]

                if 0 <= nx < 8 and 0 <= ny < 8:
                    if graph[nx][ny] == '.':
                        q.append((nx, ny))
        graph.pop()
        graph.appendleft(['.', '.', '.', '.', '.', '.', '.', '.'])
        turn += 1
        
        if turn == 9:
            return 1
    return 0
            
print(main())

문제풀이

BFS의 개념만 알면 쉽게 풀 수 있는 문제다.

다만 벽을 한행씩 내려가는 작업을 일일히 한칸 내려서 변경하는 방법보다, 맨 밑 행을 아예 삭제해버리고 새로운 행을 맨위에 추가해주는 방법을 사용하면 훨씬 간결하게 코드를 작성 할 수 있다!