백준 16954 움직이는 미로 탈출 python

미로의 벽이 초당 1칸씩 밑으로 내려온다. 이때 캐릭터가 (7, 0)의 위치에서 (0, 7)로 이동할수 있는 묻는 문제이다.
벽이 순환한다면 생각을 좀 다르게 해야겠지만 이 문제에서는 범위를 벗어난 벽은 사라지기 때문에 쉽게 접근할 수 있었다.

📜 문제 바로 가기 : 움직이는 미로 탈출

제출코드

파이썬

import sys
input = sys.stdin.readline

time_maze = {0 : [input().rstrip() for _ in range(8)]}

for i in range(1, 9):
    mirro = time_maze[i-1]
    mirro = ["........"] + mirro[:7]
    time_maze[i] = mirro

ans = 0
delta =[(1, 0), (-1, 0), (0, 1), (0, -1), (-1, -1), (-1, 1), (1, 1), (1, -1), (0, 0)]

def isRange(i, j):
    if 0 <= i < 8 and 0 <= j < 8 and ans == 0:
        return True
    return False

def DFS(time, i, j):
    global ans
    if ans == 1 or time_maze[time][i][j] == "#":
        return
    
    if time == 8:
        ans = 1
        return

    for di, dj in delta:
        ni, nj = i + di, j + dj
        if isRange(ni, nj) and time_maze[time][ni][nj] != "#":
            DFS(time+1, ni, nj)

DFS(0, 7, 0)
print(ans)

---

접근방법

생각을 해보면 끝까지 내려온 벽은 다음에 없어진다.
미로의 크기가 8x8 로 고정이므로 우리는 8초까지만 미로를 보면 된다.
8초 이후에 미로 상태는 아무런 벽이 없는 상태의 미로가 된다.

이 말은 8초까지 미로에서 생존(?)한다면 그 이후에는 무조건 원하는 위치인 (0, 7)로 이동할 수 있다는 말이 된다.

여기서 생존이란 벽이 내려올때 내려온 위치에 캐릭터가 없다면 생존이라고 생각하면 되겠다.

이러한 조건을 가지고 DFS를 실행해주면 될 것이다!
BFS도 될거 같긴한데 목표는 8초를 버티는 것이라 DFS 가 좀 더 적합해 보인다.