[움직이는 미로 탈출/G3/Python3]

1414번  불우이웃 돕기 G3

 

문제
욱제는 학교 숙제로 크기가 8 ×8인 체스판에서 탈출하는 게임을 만들었다. 체스판의 모든 칸은 빈칸 또는 벽 중 하나이다. 욱제의 캐릭터는 가장 왼쪽 아랫 칸에 있고, 이 캐릭터는 가장 오른쪽 윗 칸으로 이동해야 한다.이 게임의 특징은 벽이 움직인다는 점이다. 1초마다 모든 벽이 아래에 있는 행으로 한 칸씩 내려가고, 가장 아래에 있어서 아래에 행이 없다면 벽이 사라지게 된다. 욱제의 캐릭터는 1초에 인접한 한 칸 또는 대각선 방향으로 인접한 한 칸으로 이동하거나, 현재 위치에 서 있을 수 있다. 이동할 때는 빈칸으로만 이동할 수 있다. 1초 동안 욱제의 캐릭터가 먼저 이동하고, 그다음 벽이 이동한다. 벽이 캐릭터가 있는 칸으로 이동하면 더 이상 캐릭터는 이동할 수 없다. 욱제의 캐릭터가 가장 오른쪽 윗 칸으로 이동할 수 있는지 없는지 구해보자.

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

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

그래프 이론, 그래프 탐색, BFS

 

 

벽이 존재할 수 있는 시간은 8초이다.

해당 시간 이후에도 플레이어가 살아 있다면 모두 빈칸이기 때문에 탈출할 수 있을 것이다.

BFS로 풀이 하였다. 배열을 여러 개 만들어서 벽 제거 - 생성이 아닌, 벽 생성만 진행하였다.

 

 

import sys
from collections import deque

map = [list(sys.stdin.readline().rstrip()) for _ in range(8)]

visit = [[[False] * 8 for _ in range(8)] for __ in range(10)]

move_list = [[0,0],[0,1],[0,-1],[1,0],[1,1],[1,-1],[-1,-1],[-1,0],[-1,1]]

pos = deque()
pos.append((7,0))
cnt = 0

wall_list = []

for i in range(8):
    for j in range(8):
        if map[i][j] == '#':
            wall_list.append([i,j])

def move_cnt(cnt):
    global wall_list
    global pos
    
    next_pos = []
    for y, x in pos:
        if map[y][x] == "#": continue
        for ay, ax in move_list:
            dy, dx = y+ay, x+ax
            if dy<0 or dx<0 or dx>=8 or dy>=8: continue
            if map[dy][dx] == '#': continue
            if visit[cnt][dy][dx]: continue
            visit[cnt][dy][dx] = True
            next_pos.append((dy, dx))
    pos = next_pos
    
    next_wall_list = []
    for y, x in wall_list:
        map[y][x] = '.'
    for y, x in wall_list:
        if y+1 >= 8: continue
        map[y+1][x] = '#'
        next_wall_list.append([y+1, x])
    wall_list = next_wall_list


for i in range(1, 9):
    move_cnt(i)
    
while pos:
    move_cnt(9)

print(1 if visit[-1][0][-1] else 0)

---