[백준] 16954 움직이는 미로 탈출 [Python, 파이썬]

• 문제 : https://www.acmicpc.net/problem/16954
• 🔑 BFS
  • 먼저 벽이 내려온 상태를 모두 만들었다. (8 개 이후는 벽이 모두 사라지기 때문에 8 개까지)
    • 이전 맵 상태를 가져와서 벽을 내리는데 이때 리스트가 얕은 복사가 되지 않게 주의
  • 그리고 이동 방향은 제자리, 상하좌우, 대각선 총 9개의 방향
  • 제자리 위치하는 방향(i = 0) 일 때도 큐에 넣을 수 있게 방문 처리를 해제했다.
    • 이것 때문에 79% 에서 막혔다가 위 조건 추가로 문제 해결
  • 현재 깊이에 맞는 벽 상태를 보고 갈 수 있는지 확인 (현재 깊이)
  • 갔다면 벽이 내려오고 나서 벽에 안 부딪히는지 확인 (현재 깊이 + 1)
  • 두 조건 만족하면 큐에 추가
  • 도착지에 도착했거나 깊이가 8 이상이 되면 정답 처리하고 끝 ✨

 

 

from collections import deque

board = [[list(input()) for _ in range(8)]]     # 처음 상태 맵

for i in range(8):                              # 벽이 내려온 맵 상태 (8개)
    tmp = [list(i) for i in board[i]]
    tmp.insert(0, ['.', '.', '.', '.', '.', '.', '.', '.'])
    tmp.pop()
    board.append(tmp)

q = deque([(7, 0, 0)])
visit = [[0] * 8 for _ in range(8)]
mx, my = [0, 1, -1, 0, 0,  1, 1, -1, -1], [0, 0, 0, 1, -1,  1, -1, 1, -1]   # 제자리, 8방향

while q:
    now_x, now_y, now_depth = q.popleft()

    if (now_x == 0 and now_y == 7) or now_depth >= 8:   # 도착지에 왔거나 깊이가 8이 넘어가면 정답
        print(1)
        exit()

    for i in range(9):
        next_x, next_y = now_x + mx[i], now_y + my[i]

        if i == 0:                                      # 제자리에 있을 수 있도록 만들어줌
            visit[next_x][next_y] = 0

        if 0 <= next_x < 8 and 0 <= next_y < 8 and visit[next_x][next_y] == 0:
            if board[now_depth][next_x][next_y] == '.':         # 현재 모양에서 갈 수 있는지
                if board[now_depth+1][next_x][next_y] != '#':   # 벽이 내려오면 안 부딪히는지
                    q.append((next_x, next_y, now_depth+1))
                    visit[next_x][next_y] = 1

print(0)