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

백준 16954번

✔️ 문제 풀이

◾ 간단한 문제 설명

• 8 X 8 칸의 맵이 주어지고, 맵에는 빈공간과 벽이 있다.
• 벽은 1초가 지날 때마다 아래로 한 칸씩 떨어진다. (테트리스처럼)
  벽은 인덱스 범위를 벗어나면 그냥 사라진다.
• (0, 7)에서 시작하여 (7, 0)까지 도달할 수 있는지 확인한다.

◾ 벽들의 인덱스를 활용

• 이동한 좌표에서 벽과 마주칠지 아닐지를 판단하기 위해서는 좌표의 실제 위치와 시간의 경과를 반영한 위치가 필요하다
• 벽은 1초에 한 칸씩 내려오기 때문에 이를 실제 좌표와 시간의 경과를 반영하여 계산하면 결국 실제 좌표 - 지난 시간에 해당하는 인덱스가 내가 지금의 이동에서 마주칠 공간의 인덱스이다.

◾ 조건 체크에 유의

• (X, Y)의 실제 위치는 인덱스 범위 내에 유효한지만 체크하고, 방문체크를 해줄 필요가 없다.
  벽을 피하기 위해서 이전에 방문했던 곳을 또 방문해야하는 케이스도 있기 때문이다.
• 하지만 시간의 경과를 반영한 위치에 대해서는 방문체크를 해줘야한다!
• 처음에는 지금 이동할 곳이 벽인지 아닌지만을 체크해서 오답처리 됐다ㅠㅠ 내가 이동한 후, 1초가 지났을 때 벽과 만나는지도 체크해줘야한다

최종 제출 코드

from collections import deque

grid = []
for _ in range(8):
  grid.append(input())

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

q = deque()
q.append((0, 7, 0))

visited = [[False]*8 for _ in range(8)]
result = 0

while q:
  x, y, times = q.popleft()

  # 오른쪽 맨 위에 도달했으면 1 출력
  if x==7 and y==0:
    result = 1
    break
  
  for i in range(9):
    nx = x+dx[i]
    ny = y+dy[i]

    if nx < 0 or ny < 0 or nx >= 8 or ny >= 8:
      continue
      
    if ny-times < 0 or ny-times >= 8:
      q.append((nx, ny, times+1))
    elif not visited[ny-times][nx] and grid[ny-times][nx] == '.' and grid[ny-(times+1)][nx] == '.':
      visited[ny-times][nx] = True
      q.append((nx, ny, times+1))
      
print(result)

✔️ 실행 결과