[BOJ] 16954. 움직이는 미로 탈출(Python) / BFS

16954번: 움직이는 미로 탈출

8X8 크기의 맵 왼쪽 하단에서 시작해 오른쪽 상단으로 탈출할 수 있는지 여부를 0과 1로 리턴하는 문제.

이 때, 욱제가 이동 후 맵 내의 벽이 한 칸씩 내려온다. 

# 1시간 31분 소요

• 사용 알고리즘 : BFS 너비 우선 탐색
• 우선, 내가 코드를 다 짜고 90%에서 계속 틀려서 반례를 살폈는데, 욱제는 이동하지 않고 제자리에 있을 수도 있다는 것이다.
• 즉, 8방향 + 제자리까지 해서 총 9개의 방향 델타 좌표를 탐색해야한다는 것!
• 벽이 움직이는 것은 처음에 맵을 받을 때 deque으로 받는다.
• bfs 함수 안을 살펴보면,
  • 먼저 첫 위치를 큐에 담고, 큐에 값이 있는 동안 
  • 한 번 while문 실행할 때마다 현재 큐의 길이만큼 for문을 돌려 다음 턴과 구분해준다.(time 변수 활용을 위해)
  • 큐에서 좌표값을 꺼내는데, 해당 위치가 이미 벽이라면 이동 자체가 불가하므로 넘긴다.
  • 큐에서 꺼낸 좌표값이 우측 상단 (0, 7)이라면 탈출 성공으로 1을 리턴한다.
  •  제자리를 포함한 9방향에 대해 이동할 위치가 격자 밖이거나 벽 또는 이미 방문했다면 넘긴다.
  • 이를 통과했다면 이동 가능한 것이므로 큐에 담고 해당 턴에 방문한 곳을 또 방문하지 않기 위해 visited에 표시한다.
  • for문이 끝났다면 해당 초에 욱제가 이동한 곳이 모두 큐에 담기고 이동을 완료했다면,
  • 벽을 아래로 움직인다.
    • 현재 맵의 상태를 표현한 board는 deque이므로 마지막 리스트를 pop해주고 appendleft로 빈 공간으로 이뤄진 리스트를 덱의 앞부분에 새로 삽입해준다.
  • 벽의 이동도 완료했다면 시간을 time+1 해준다.
  • 8초 후에는 맵에 벽이 없으므로 탈출 가능 1을 리턴한다.(while문 빨리 탈출할 수 있도록 time 설치)
• 큐에 담긴 모든 값에 대해 탐색했음에도 목적지에 도달하지 못했다면 0을 리턴한다.

 

파이썬 코드는 다음과 같다.

---

from sys import stdin
input = stdin.readline
from collections import deque

# 9방향
dr = (0, -1, 0, 1, 1, 1, 0, -1, -1)
dc = (0, 1, 1, 1, 0, -1, -1, -1, 0)

def bfs():
    Q = deque([(7, 0)])
    time = 0
    while Q:
        visited = [[0] * 8 for _ in range(8)]
        qlen = len(Q)
        for _ in range(qlen):
            r, c = Q.popleft()
            if board[r][c] == "#":  # 이동 시작 위치가 벽이면
                continue
            if (r, c) == (0, 7):    # 탈출 성공
                return 1

            for d in range(9):
                nr = r + dr[d]
                nc = c + dc[d]
                # 격자 밖으로 나가면
                if not (0 <= nr < 8 and 0 <= nc < 8):
                    continue
                # 이동할 위치가 벽이거나 이미 방문했으면
                if board[nr][nc] == "#" or visited[nr][nc]:
                    continue
                visited[nr][nc] = 1
                Q.append((nr, nc))
        
        # 벽 이동
        board.pop()
        board.appendleft(['.', '.', '.', '.', '.', '.', '.', '.'])

        time += 1
        if time == 9:   # 9초 후 현존하는 벽 없으므로 탈출 가능
            return 1
    return 0    # 탈출 실패

# main
board = deque(list(input().rstrip()) for _ in range(8))
print(bfs())

---

• 시간 : 140ms / 메모리 : 125372kb
• 고찰 : 코드를 정말 빨리 짰는데, 계속 92%틀려서 여러 번 코드를 봤다.. time이 8초가 아니라 9초가 될 때 1을 출력해야 한다. 또한, 제자리도 고려해야 했다는 점.. 그래도 나름 재밌게 풀었던 문제다! BFS 문제 요새 많이 풀면서 감을 많이 잡았다. Keep Going.