[백준] 16954번 움직이는 미로탈출 (파이썬)

문제링크 : https://www.acmicpc.net/problem/16954

난이도: GOLD III

문제해결 아이디어

• 하나의 큐를 순회하는 동안은 보드의 모양이 같다.
• 시간이 9초 이상이면 벽이 없으므로 return 1
• wall 들의 좌표값을 갖고있고 한칸씩 내려서 표현?
• walls는 in 메소드를 통해 존재 여부만 확인하므로 set 자료형 사용

소스코드

import sys
from itertools import product
from collections import deque

input = sys.stdin.readline

# 가동범위 : 상하좌우, 대각선, 제자리
# 벽은 1초마다 한칸씩 내려감
# 욱제가 먼저 이동하고 캐릭터가 이동
# 벽이랑 욱제가 만나면 욱제는 이동x

# 하나의 큐를 순회하는 동안은 보드의 모양이 같다.
# 시간이 9초 이상이면 벽이 없으므로 return 1
# wall 들의 좌표값을 갖고있고 한칸씩 내려서 표현?
# walls는 in 메소드를 통해 존재 여부만 확인하므로 set 자료형 사용

board = []

for _ in range(8):
    board.append(list(input().strip()))

walls = set()

for i in range(8):
    for j in range(8):
        if board[i][j] == '#':
            walls.add((i, j))

dir = list(product((-1, 0, 1), repeat=2))  # 방향 설정
q = deque()
q.append((7, 0))
time = 0
while q:
    visited = [[False] * 8 for _ in range(8)]
    for _ in range(len(q)):  # for문을 순회하는 동안은 같은 모양의 board를 사용중
        x, y = q.popleft()
        if (x, y) == (0, 7):
            print(1)
            exit()

        if (x, y) in walls:
            continue

        for i in range(9):
            nx = x + dir[i][0]
            ny = y + dir[i][1]

            if 0 <= nx < 8 and 0 <= ny < 8 and (nx,ny) not in walls and not visited[nx][ny]:
                visited[nx][ny] = 1
                q.append((nx, ny))

    new_walls = set()

    for x, y in walls:
        if x < 7:
            new_walls.add((x + 1, y))

    walls = new_walls
    time += 1

    if time == 9:
        print(1)
        exit()

print(0)