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

BFS

문제 : 벽 부수고 이동하기

BFS 문제 입니다.
하지만 여기서 기존의 문제와 다른점은 "만약에 이동하는 도중에 한 개의 벽을 부수고 이동하는 것이 좀 더 경로가 짧아진다면, 벽을 한 개 까지 부수고 이동하여도 된다." 라는 조건이 추가되어 있다는 것입니다.

그러면 우리는 다음의 두가지 방법을 생각해야 합니다.
1. 이동 할 수 없고, 벽을 부술 수 있으며 다음 칸을 방문할 수 있는가?
2. 이동 할 수 있고, 벽을 부술 수 없으며 다음 칸을 방문 할 수 있는가?

벽을 부수면 계속 이동할 수 있고, 이전의 이동했던 최단거리에 더해져야 하기 때문에 이를 3차원 배열로 나타내어 벽을 부술 수 있는 상태와 없는 상태로 로 나타내면 쉽게 풀 수 있습니다.

import sys
from collections import deque

input = sys.stdin.readline
n, m = map(int, input().split())
lst = []
for i in range(n):
	lst.append(list(map(int, sys.stdin.readline().rstrip())))

dx = [-1, 1, 0, 0]
dy = [0, 0, -1, 1]
def bfs(a, b, visited):

	q = deque()
	q.append((a, b, visited))
    # 벽이 있는 것과 없는 걸로 나누기 
	check = [[[0]*2 for _ in range(m)] for _ in range(n)]
	check[0][0][1] = 1
	while q:
		x, y, v = q.popleft()
        # 출력 조건 
		if x == n-1 and y == m-1:
			return check[n-1][m-1][v]
		for i in range(4):
			nx = x + dx[i]
			ny = y + dy[i]
			if nx < 0 or ny < 0 or nx >= n or ny >= m:
				continue
            # 벽이 있고 부술 수 있으며 다음 칸을 방문할 수 있다. (중복체크)
			if lst[nx][ny] == 1 and v > 0 and check[nx][ny][v-1] == 0:
				check[nx][ny][v-1] = check[x][y][v] + 1
				q.append((nx, ny, v-1))
            # 벽이 없고 다음 칸을 방문 할 수 있다 ( 중복체크) 
			if lst[nx][ny] == 0 and check[nx][ny][v] == 0:
				check[nx][ny][v] = check[x][y][v] + 1
				q.append((nx, ny, v))
    # 없으면 -1
	return -1

print(bfs(0, 0, 1))