BaekJoon2206_벽 부수고 이동하기

문제

풀이

어려운 문제였다. 벽을 부수며 이동하였을 때 벽을 부순 경우와 부수지 않았을 경우를 어떻게 나누어야 하는지 한참을 고민했는데 결국 스스로 해결하진 못했다..
다른 풀이를 참고한 결과 visited 배열에 벽을 부쉈을 경우를 추가하여 3차원 배열로 만들어 해결할 수 있었다.
벽을 부수지 않고 이동하면 0을 저장하고 부쉈을 경우에는 1을 저장하며 진행한다. 부수지 않았을 경우와 부쉈을 경우를 계속해서 큐에 넣어가며 진행하면서 먼저 가장 끝에 도착하였을때의 이동 칸수를 출력하면 된다.

풀이 코드

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

n, m = map(int,input().split())
graph = []

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

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

def bfs(a,b,c):
    queue = deque()
    queue.append((a,b,c))

    while queue:
        x,y,z = queue.popleft()

        if x == n-1 and y == m-1:
            return visited[x][y][z]
        
        for i in range(4):
            nx = x + dx[i]
            ny = y + dy[i]
            if 0 <= nx < n and 0 <= ny < m:
                if graph[nx][ny] == 1 and z == 0:
                    visited[nx][ny][1] = visited[x][y][0] + 1
                    queue.append((nx,ny,1))
                elif graph[nx][ny] == 0 and visited[nx][ny][z] == 0:
                    visited[nx][ny][z] = visited[x][y][z] + 1
                    queue.append((nx,ny,z))
    return -1

print(bfs(0,0,0))