[Python] 백준 (움직이는 미로 탈출) 16954

문제

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

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

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

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

입력

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

출력

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

예제 입력 1

........
........
........
........
........
........
........
........

예제 출력 1

1

예제 입력 2

........
........ 
........ 
........ 
........
........ 
##......
........

예제 출력 2 복사

0

---

문제풀이

• bfs를 사용하여 푼 문제
• 한번 이동할때마다 벽이 내려오는 함수를 구현한다.(moveWall)
• queue에 시작포인트를 넣는다.
• 욱제의 현재위치(currentPoint)에서 갈 수 있는 곳을 찾아 큐에 추가한다.(이동하는 지점에 벽이 없어야함, 이동하는 지점 위에 벽이 없어야 함, 0<=행<=7, 0<=열<=7)
• 만약 이동한 행이 0(첫번째 줄)에 도달하면 미로를 탈출한 것이다.

import sys
from collections import deque

chess = []

currentPoint = (7,0)
move = [(0,0), (1,0),(-1,0),(0,-1),(0,1), (1,-1),(1,1),(-1,-1),(-1,1)] #제자리, 상,하,좌,우, 대(상좌),대(상우),대(하좌),대(하우)

# 체스판 상태 입력
for i in range(8):
    chess.append(list(sys.stdin.readline().rstrip()))

# moveWall이 호출되면 벽이 1칸씩 내려옴
def moveWall(chess):
    a = '........'
    chess.insert(0, list(a))
    chess.pop()
    return chess

def bfs(chess, currentPoint):
    queue = deque()
    queue.append(currentPoint)
    while queue:
        for _ in range(len(queue)):
            temp = queue.popleft()
            for i in move:
                currentPoint = temp
                movePoint = tuple(sum(elem) for elem in zip(currentPoint, i))
                if movePoint[0] <= 7 and movePoint[0] >= 0 and movePoint[1] <= 7 and movePoint[1] >= 0:
                    if chess[movePoint[0]][movePoint[1]] != '#' and chess[movePoint[0]-1][movePoint[1]] != '#':
                        if movePoint[0] == 0:
                            return 1
                        queue.append(movePoint)
        moveWall(chess)
    return 0

print(bfs(chess, currentPoint))