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

from collections import deque

n, m = map(int,input().split())

maze = [list(map(int,list(input()))) for _ in range(n)]

visited = [[[0]*m for _ in range(n)] for _ in range(2)]

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

def bfs():
    
    visited[0][0][0] = 1
    
    queue = deque([(0,0,0)])

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

        if x == n-1 and y == m-1:
            return visited[w][x][y]

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

print(bfs())

이번 문제는 (0,0) 위치에서 (N,M) 로 이동하기 위한 최소 이동 칸 수를 구하되, 더 빨리 도달할 수 있다면 벽을 1개까지 부술 수 있다는 조건이 있는 문제이다.

 

바로 이전에 풀었던 미로 탈출 문제(https://woohyun-king.tistory.com/196)와 거의 동일한 문제로, (0,0)에서 시작하여 (N,M)를 도착 지점으로 한다는 점과 시작하는 칸도 카운팅을 한다는 점만 차이가 있다.

 

최단 거리를 구하기 위한 BFS 알고리즘과 벽을 부순 상황에 따라 두 가지 2차원 배열로 구별하여 이동경로를 기록한다는 점을 이용하여 풀이할 수 있는 문제였다 :)