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

https://www.acmicpc.net/problem/2206

2206번: 벽 부수고 이동하기

3차원 배열을 이용하여 BFS를 해야하는 문제입니다. 단순하게 [벽을 부쉈는지 여부][y][x]로 정의하고 각각의 상태에서 가질 수 있는 최소 거리를 저장해두면 된다. 즉, 벽을 부수고 도달할 수 있는 최단거리와 벽을 부수지 않고 도달할 수 있는 최단 거리중 더 짧은 거리를 답으로 출력하면 된다.

 

import sys
from collections import deque

input = sys.stdin.readline

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

INT_MAX = sys.maxsize

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

def in_range(y, x):
    return 0 <= y < n and 0 <= x < m


def bfs():
    dys = [0, 1, 0, -1]
    dxs = [1, 0, -1, 0]

    q = deque([(0, 0, 0, 0)])

    # visited[isBroke][y][x] : isBroke -> 0(벽을 깨지 않고) 1(벽을 깼을 때)
    # (y, x)에 도달했을 때 가질 수 있는 최단 거리
    visited = [
        [[INT_MAX] * m
        for _ in range(n)]
        for __ in range(2)
    ]

    # 시작점 초기화
    visited[0][0][0] = 0

    while q:
        dist, isBroke, y, x = q.popleft()

        for dy, dx in zip(dys, dxs):
            ny = y + dy
            nx = x + dx

            if in_range(ny, nx):
                # 벽을 이미 깬 경우
                if isBroke == 1:
                    # 다음이 벽이 아닌 경우에만 큐에 넣어줌
                    if board[ny][nx] == 0 and visited[isBroke][ny][nx] > dist + 1:
                        visited[isBroke][ny][nx] = dist + 1
                        q.append((dist + 1, isBroke, ny, nx))

                # 벽을 깨지 않은 경우
                else:
                    # 다음이 벽인 경우
                    if board[ny][nx] == 1 and visited[1][ny][nx] > dist + 1:
                        visited[1][ny][nx] = dist + 1
                        q.append((dist + 1, 1, ny, nx))
                    # 다음이 벽이 아닌 경우
                    elif board[ny][nx] == 0 and visited[0][ny][nx] > dist + 1:
                        visited[0][ny][nx] = dist + 1
                        q.append((dist + 1, 0, ny, nx))

    return min(visited[0][n - 1][m - 1], visited[1][n - 1][m - 1])


ans = bfs()

if ans == INT_MAX:
    print(-1)
else:
    print(ans + 1)