[Baekjoon] 움직이는 미로 탈출(python)

https://www.acmicpc.net/problem/16954

문제 접근

BFS를 이용하여 시작점부터 도착점까지 이동할 수 있는지 판별하는 문제이다.

 

일반적인 BFS 문제와 다른점은 4방향 탐색이 아닌 현재위치를 포함하여 9방향 탐색을 하는 것이고 탐색을 하는 중간에 배열의 상태가 바뀐다는 것이다.

---

풀이 과정

9방향 BFS를 구현해주면 된다.

 

일반적으로 BFS를 구현하면 아래처럼 구현할 것이다.

def bfs(x, y):
    while q:
        x, y = q.popleft()

        for i in range(4):
            nx = x + dx[i]
            ny = y + dy[i]

            if (
                    nx < 0
                    or nx >= 8
                    or ny < 0
                    or ny >= 8
                    or chess[nx][ny] == "#"
                    or visited[nx][ny]
                ):
                    continue

                q.append([nx, ny])
                visited[nx][ny] = True

하지만 이 문제는 1초마다 배열의 상태가 바뀌므로 현재 큐에 들어있는 좌표들을 모두 같은 루프 안에서 처리해야 한다.

 

또 좌표에 대한 처리가 끝나면 모든 벽은 아래로 한칸씩 이동해야 하므로, 간단하게 처리하기 위해 이중 리스트의 마지막 인덱스를 삭제해주고 빈 리스트를 앞에 추가해주었다.

def bfs(x, y):
    global chess

    q = deque()
    q.append([x, y])

    while q:
        visited = [[False] * 8 for _ in range(8)]

        # 1초에 해당하는 작업을 한 번에 처리
        for _ in range(len(q)):
            x, y = q.popleft()

            if chess[x][y] == "#":
                continue

            if x == 0 and y == 7:
                return 1

            for i in range(9):
                nx = x + dx[i]
                ny = y + dy[i]

                if (
                    nx < 0
                    or nx >= 8
                    or ny < 0
                    or ny >= 8
                    or chess[nx][ny] == "#"
                    or visited[nx][ny]
                ):
                    continue

                q.append([nx, ny])
                visited[nx][ny] = True

        # 벽들을 한칸씩 이동
        chess.pop()
        chess.insert(0, [".", ".", ".", ".", ".", ".", ".", "."])

---

정답 코드

"""
    백준 16954번 움직이는 미로 탈출
"""
import sys
from collections import deque

chess = [list(sys.stdin.readline()[:-1]) for _ in range(8)]
dx = [-1, 0, 1, -1, 0, 1, -1, 0, 1]
dy = [-1, -1, -1, 0, 0, 0, 1, 1, 1]


def bfs(x, y):
    global chess

    q = deque()
    q.append([x, y])

    while q:
        visited = [[False] * 8 for _ in range(8)]

        for _ in range(len(q)):
            x, y = q.popleft()

            if chess[x][y] == "#":
                continue

            if x == 0 and y == 7:
                return 1

            for i in range(9):
                nx = x + dx[i]
                ny = y + dy[i]

                if (
                    nx < 0
                    or nx >= 8
                    or ny < 0
                    or ny >= 8
                    or chess[nx][ny] == "#"
                    or visited[nx][ny]
                ):
                    continue

                q.append([nx, ny])
                visited[nx][ny] = True

        chess.pop()
        chess.insert(0, [".", ".", ".", ".", ".", ".", ".", "."])

    return 0


print(bfs(7, 0))