[python] 벽 부수고 이동하기_백준 2206번(bfs)

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

이 문제도 최소 이동 거리를 구하는 문제이기 때문에 bfs로 방향을 잡고 풀면 된다.
다만 여기서 다른 문제와는 다른 점은 딱 한번 벽을 부술 수 있다는 것이다.
벽을 부순 경우와 안 부순 경우를 기록해가기 위해 2차원 배열이 아닌 3차원 배열의 그래프로 구현했다.

solution

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)]
visited[0][0][0] = 1

for i in range(n):
    graph.append(list(input().rstrip()))

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


def bfs(x, y, z):
    queue = deque()
    queue.append((x, y, z))

    while queue:
        a, b, c = queue.popleft()
        if a == n - 1 and b == m - 1:
            return visited[a][b][c]
        for i in range(4):
            nx = a + dx[i]
            ny = b + dy[i]
            if nx < 0 or nx >= n or ny < 0 or ny >= m:
                continue
            if graph[nx][ny] == '1' and c == 0 :
                visited[nx][ny][1] = visited[a][b][0] + 1
                queue.append((nx, ny, 1))
            elif graph[nx][ny] == '0' and visited[nx][ny][c] == 0:
                visited[nx][ny][c] = visited[a][b][c] + 1
                queue.append((nx, ny, c))
    return -1


print(bfs(0, 0, 0))