[백준] 2206번 벽 부수고 이동하기

이 문제는 bfs()를 수행할 때 두 가지 조건의 경우에만 queue에 원소를 넣으면 원하는대로 알고리즘을 수행할 수 있다.
1. 벽을 깨지 않았고 벽이 있을 경우
2. 벽이 없는 경우

최단 경로를 출력하려면 bfs 알고리즘을 수행한 경로, 즉 visited 배열을 만들어 갱신하면 된다.

그래서 생각한 방법이 visited 배열을 3차원으로 제작하는 것이다. (1)visited[x][y][0]는 벽을 깨지 않았을 경우의 방문 여부를 나타내고 (2)visited[x][y][1]은 벽을 깼을 경우의 방문 여부를 나타낸다.

1번의 경우에는 이전까지 기록한 (1)의 방문 횟수에 새로운 방문 횟수를 추가하여 (2)에 기록해준다. 2번의 경우에는 (1)이나 (2)에 계속하여 방문 횟수를 기록해주는 경우이다.

테스트 케이스 2번을 수행한 visited 배열은 다음과 같다.

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

n, m = map(int, input().split())
graph = []
visited = [[[0] * 2 for _ in range(m)] for _ in range(n)]
for _ in range(n):
  graph.append(list(map(int, input().rstrip())))

dx = [-1, 0, 1, 0]
dy = [0, -1, 0, 1]
q = deque([(0, 0, 0)])
visited[0][0][0] = 1

def bfs():
  while q:
    x, y, z = q.popleft()
    if x == n-1 and y == m-1:
      return visited[x][y][z]
    for i in range(4):
      rx = x + dx[i]
      ry = y + dy[i]
      if 0 <= rx < n and 0 <= ry < m:
        # q에 원소 넣고 visited 갱신
        if graph[rx][ry] == 1 and z == 0: # 벽을 깨지 않았고 벽이 있을 경우
          visited[rx][ry][1] = visited[x][y][0] + 1
          q.append((rx, ry, 1))
        elif graph[rx][ry] == 0 and not visited[rx][ry][z]: # 벽이 없는 경우
          visited[rx][ry][z] = visited[x][y][z] + 1
          q.append((rx, ry, z))
  return -1

print(bfs())