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

1. 문제 - 백준 16954 움직이는 미로 탈출

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

 

💡알고리즘 - BFS

• 시작점(7,0)이 있고 도착점(0,7)이 있고 그래프 탐색이라는 점에서 DFS, BFS를 활용할 수 있다. 필자는 BFS가 더 편해서 BFS 사용

✅ 풀이

from collections import deque

dx = [-1, 1, 0, 0, -1, -1, 1, 1, 0]
dy = [0, 0, -1, 1, -1, 1, -1, 1, 0]  # 인접한 한칸 혹은 대각선 방향, 현재 위치에 서있을 수 있음

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

# board에서 벽 아래로 이동하는 함수 하나 필요
def move_wall(board):
    new = [['.'] * 8 for _ in range(8)]
    for i in range(8):
        for j in range(8):
            if board[i][j] == '#':
                if i + 1 < 8:
                    new[i+1][j] = '#'
    return new

def bfs():
  q = deque([(7, 0)])

  # 1초마다
  while q:
    # 욱제의 캐릭터가 움직인 후에
    # 이때 board가 바뀌므로 visited도 초기화해야한다.
    visited = [[False] * 8 for _ in range(8)]
    
    # 매 초마다 바뀐 board에서 현재 q의 후보들 중 욱제의 캐릭터가 이동할 수 있는 경우의 수
    for _ in range(len(q)):
      x, y = q.popleft()
      if board[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 0<=nx<8 and 0<=ny<8 and not visited[nx][ny] and board[nx][ny] == '.':
            q.append((nx, ny))
            visited[nx][ny] = True

    # 벽이 움직인다. -> board가 바뀐다.
    board[:] = move_wall(board)

  return 0

print(bfs())

 

- 매번 1초마다 보드에 있는 벽이 아래로 이동하므로, 이를 함수화한다. (move_wall 함수)

- while q: 1초마다의 시간 흐름을 나타냄

- visited를 매초마다 초기화하는 이유는, 매초마다 벽이 이동하면서 board가 달라지므로 visited도 달라지기 때문에, 이에 따라 새롭게 탐색해야하기 때문이다.

- q에 있는 욱제의 캐릭터가 탐색하는 좌표들이 벽이 이동하여 새로운 board에서도 탐색이 가능한지를 확인해야하므로, q의 길이만큼 탐색을 진행한다.

 

 

⭐️ 새롭게 알게된 점

    board[:] = move_wall(board)

 

배열을 복사할 때, board = move_wall(board)로 하게되면 python에서는 덮어쓰기가 아니라 '참조'의 형태가 되므로

덮어쓰기를 위해 위와같이 덮어쓰기한다.