벽 부수고 이동하기[백준 2206](파이썬)

문제

---

벽 부수고 이동하기 [백준 2206]
https://www.acmicpc.net/problem/2206

풀이

---

너비 우선 탐색으로 큐에 다음 좌표와 거리 정보, 벽을 부셨는 지 아닌 지를 나타내는 정보를 넣어주는 방식을 택했다. 큐가 계속해서 쌓이는 것을 방지하기 위해서 visited 리스트를 이용하려 했는데 벽을 부셨을 때와 안 부셨을 때 둘 다 탐색이 되므로 구별하는 것이 필요했다. 그래서 visited 배열을 3차원으로 선언해서 부수고 들리는 것과 아닌 것을 구별했다.

코드

---

from collections import deque
n, m = map(int, input().split())
board = [[int(i) for i in list(input())] for _ in range(n)]
visited = [[[0, 0] for _ in range(m)] for _ in range(n)]
dx = [0, 0, -1, 1]
dy = [1, -1, 0, 0]
q = deque()
q.append((0, 0, 1, 0))
visited[0][0][0] = 1
min_time = n * m + 1
while q:
    x, y, dist, breaker = q.popleft()
    if x == n - 1 and y == m - 1:
        min_time = min(min_time , dist)
    for d in range(4):
        nx = x + dx[d]
        ny = y + dy[d]
        if 0 <= nx < n and 0 <= ny < m:
            if board[nx][ny] == 1 and not breaker:
                q.append((nx, ny, dist + 1, breaker + 1))
                visited[nx][ny][breaker + 1] = 1
            elif board[nx][ny] == 0 and not visited[nx][ny][breaker]:
                q.append((nx, ny, dist + 1, breaker))
                visited[nx][ny][breaker] = 1
if min_time == n * m + 1:
    print(-1)
else:
    print(min_time)