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

 

 

아이디어

 

체스판을 갱신하며 9초 이상 캐릭터가 이동할 수 있는지 확인한다.

 

 

풀이

 

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

def solution():
    board = [[*input()] for _ in range(8)]
    visited = [[0]*8 for _ in range(8)]
    visited[7][0] = 1
    stack = [(7, 0)]
    t = 1
    while stack and t < 9:
        _stack = []
        while stack:
            r, c = stack.pop()
            for dr, dc in delta:
                nr, nc = r+dr, c+dc
                if 8 > nr >= 0 and 8 > nc >= 0:
                    if visited[nr][nc] <= t:
                        if board[nr][nc] == '.' and (nr == 0 or board[nr-1][nc] == '.'):
                            visited[nr][nc] = t+1
                            _stack.append((nr, nc))
        board.pop()
        board = [['.']*8]+board
        stack = _stack
        t += 1
    print((t > 8)*1)

solution()