[백준 BOJ_2206] 벽 부수고 이동하기 Python 풀이

출처: 백준 온라인 저지

문제

풀이

BFS로 풀어주었습니다.

visited를 다음과 같은 3차원 배열로 만들어줍니다.

• visited[y][x][0] = 좌표 (x, y)까지의 벽을 부수지 않은 상태에서의 최단 경로
• visited[y][x][1] = 좌표 (x, y)까지 이미 벽을 하나 부수고 난 뒤의 상태에서의 최단 경로

가장 첫 번째 좌표가 되는 (0, 0)에는 벽이 없다는 가정이므로 visited[0][0][0]을 1로 저장해준 뒤 BFS를 돌아줍니다. queue에 들어가는 정보는 다음과 같습니다.

• y 좌표, x 좌표, broken broken에는 여태까지 벽을 부수었는지에 대한 여부를 담아줍니다. 처음에는 아무 벽도 부수지 않았으므로 0으로 초기화해줍니다.

queue에 append를 해주는 경우는 다음과 같습니다.

• 벽을 부수지 않았고, 좌표에 벽이 있다면 새로운 좌표에 현재 좌표에서 1을 더한 값을 저장한 뒤, broken의 값은 1로 queue에 append
• 벽이 없고, 방문한 적이 없었을 때 broken의 값을 바꾸지 않고, 새로운 좌표에 현재 좌표에서 1을 더한 값을 저장한 뒤 queue에 append

이렇게 BFS를 돌아주고 난 뒤에는 visited의 broken 여부에 따른 마지막 좌표값을 확인해주면 됩니다. 만약 마지막 좌표의 값이 0이라면 도달하지 못했으므로 -1을 출력해줍니다.

코드

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

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

N, M = map(int, input().split())
graph = [list(map(int, list(input().rstrip()))) for _ in range(N)]

visited = [[[0, 0] for _ in range(M)] for _ in range(N)]
visited[0][0][0] = 1

queue = deque([(0, 0, 0)])
broken = 0

while queue:
  y, x, broken = queue.popleft()
  if y == N-1 and x == M-1:
    break
  for i in range(4):
    ny, nx = y+dy[i], x+dx[i]
    if 0 <= ny < N and 0 <= nx < M:
      if not broken and graph[ny][nx]:
        visited[ny][nx][1] = visited[y][x][0] + 1
        queue.append((ny, nx, 1))
      elif not graph[ny][nx] and not visited[ny][nx][broken]:
        visited[ny][nx][broken] = visited[y][x][broken] + 1
        queue.append((ny, nx, broken))

print(visited[N-1][M-1][broken] if visited[N-1][M-1][broken] else -1)