백준 16954 문제 분석 python

🐒 움직이는 미로 탈출

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

✍ 나의 풀이

from collections import deque


dx = [-1,-1,-1,0,0,0,1,1,1]
dy = [-1,0,1,-1,0,1,-1,0,1]

def bfs():
    queue = deque()
    queue.append((7,0))
    time = 0

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

        for _ in range(len(queue)):
            a, b = queue.popleft()
            #print(time, (a,b))
            if matrix[a][b] == -1:
                continue
            if (a,b) == (0,7):
                return 1

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

                if not (0 <= nx < 8 and 0 <= ny < 8):
                        continue
                if matrix[nx][ny] == -1 or visited[nx][ny]:
                        continue
                visited[nx][ny] = True
                queue.append((nx,ny))
        
        matrix.pop()
        matrix.appendleft([0]*8)

        time += 1
        if time == 9:
            return 1
    return 0

matrix = deque([[]for _ in range(8)])
for i in range(8):
    for j in input():
        if j == '.':
            matrix[i].append(0)
        else:
            matrix[i].append(-1)

print(bfs())

참고한 풀이

🧠 문제 이해

참고한 풀이에서는 1초가 지날떄마다 벽이 아래로 내려오는것을 구현할떄
deque을 이용해 마지막 줄을 삭제하고 맨 앞에 빈칸으로 채워진 줄을 추가했다.

그리고 bfs함수의 while문안에 for문이 있어서 의아했는데
queue의 길이를 비동기적으로 받는줄 알고 이해를 못했는데 시험해보니 루프가 끝날때까지 queue의 길이를 받아오지 않는다.

따라서 1초마다 이동할수있는 경우의 수를 찾고 방문기록을 초기화할 수 있다.

9초가 지나면 모든 벽이 사라진 뒤이다. 따라서 9초가 지나서 캐릭터가 생존하기만 하면 미로를 탈출할 수 있다.