문제

[백준] 벽 부수고 이동하기 (Gold 3)

요약

NxM 행렬로 표현되는 맵이 있다. (1, 1)에서 (N, M)까지 최단경로로 이동하려고 한다. 벽을 한 개까지 부수는 것이 허락된다. 최단 경로의 거리를 구하라.

분류

  • BFS

풀이

1. 내 풀이 (BFS)


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

n, m = map(int, input().split())
arr = [
    list(map(int, list(input().rstrip()))) for _ in range(n)
]

visited = [[[False, False]
            for _ in range(m)] for _ in range(n)]  # 벽 깬 사람, 벽 안 깬 사람

queue = deque([(0, 0, 1, True)])

dx, dy = [0, 1, 0, -1], [1, 0, -1, 0]
ans = sys.maxsize
while queue:
    r, c, cnt, flag = queue.popleft()
    if r == n - 1 and c == m - 1:
        ans = min(ans, cnt)
        break

    if (visited[r][c][0] and not flag) or visited[r][c][1]:
        continue
    visited[r][c][0] = True
    if flag:  # 벽 안 깬 사람도 지나갔으면 True로
        visited[r][c][1] = True

    for i in range(4):
        nr, nc = r + dy[i], c + dx[i]

        if 0 <= nr < n and 0 <= nc < m:
            if flag:  # 벽 안 깬 사람
                if arr[nr][nc] == 1 and not visited[nr][nc][0]:
                    queue.append((nr, nc, cnt + 1, False))
                elif arr[nr][nc] == 0 and not visited[nr][nc][1]:
                    queue.append((nr, nc, cnt + 1, flag))

            else:  # 벽 깬 사람
                if arr[nr][nc] == 0 and not visited[nr][nc][0]:
                    queue.append((nr, nc, cnt + 1, flag))

print(ans if ans != sys.maxsize else -1)