제2회 곰곰컵에서 0-1 BFS를 사용하는 문제가 나왔다. 그래서 이참에 0-1 BFS를 확실하게 알아두었다.
그 기념으로 0-1 BFS 기본 문제!

BOJ 1261 - 알고스팟 링크
(2022.12.05 기준 G4)

문제

N * M 크기의 미로는 빈 방 또는 벽으로 이루어져 있다.
(1, 1)에서 (N, M)으로 이동하기 위해 부숴야 하는 벽의 최소 개수 출력

알고리즘

가중치는 0이나 1이다. 그러므로 0-1 BFS

풀이

0-1 BFS는 다익스트라에 BFS 한 방울 흘린 것이다.
다익스트라는 최소 힙을 사용하여 현재 최단 거리인 요소를 뽑아 다시 거리를 갱신해나가는 것이다.
BFS는 거리를 갱신한 순서대로 다시 갱신해 나가는 것이다.

이 둘을 합치면?
임의로 가중치에 따라 거리를 갱신하여 덱의 맨 앞이나 뒤에 넣는 것이다.
당연히, 가중치가 0이면 맨 앞. 1이면 맨 뒤에 넣는 것이 시간복잡도 상으로 좋을 것이다.
그래서 0-1 BFS는 가중치가 0이나 1일 때만 사용 가능하다.

기본 틀은 다익스트라와 유사하다.
다만, 큐의 형태는 힙이 아니라 덱을, 갱신 후 덱에 넣을 때에는 가중치에 따라 맨 앞이나 뒤에 넣으면 된다.

코드를 보면 바로 이해가 갈 것이다.

코드

import sys; input = sys.stdin.readline
from math import inf
from collections import deque

def solve():
    M, N = map(int, input().split())
    matrix = [input().strip() for _ in range(N)]

    # 시작점은 (0, 0)
    queue = deque([[0, 0, 0]])
    distance = [[inf] * M for _ in range(N)]
    distance[0][0] = 0

    while queue:
        br, n, m = queue.popleft() # 부순 횟수, 좌표
        if distance[n][m] < br: # 현재 루트가 더 많이 부숴 온 루트이면 탐색할 필요가 없다.
            continue
        for nn, mm in [(n - 1, m), (n + 1, m), (n, m - 1), (n, m + 1)]: # 상하좌우
            if 0 <= nn < N and 0 <= mm < M:
                if matrix[nn][mm] == '1': # 다음 장소가 벽이라면 부숴야 한다.
                    if distance[nn][mm] > br + 1: # 다음 장소에 저장되어 있는 최단 거리와 비교하여 갱신
                        distance[nn][mm] = br + 1
                        queue.append([br + 1, nn, mm]) # 덱 맨 뒤에 넣자.
                else: # 다음 장소가 빈 방이라면 부수지 않아도 된다.
                    if distance[nn][mm] > br: # 다음 장소에 저장되어 있는 최단 거리와 비교하여 갱신
                        distance[nn][mm] = br
                        queue.appendleft([br, nn, mm]) # 덱 맨 앞에 넣자.

    print(distance[-1][-1])

solve()

여담

0-1 BFS는 많이 쓰이지는 않는 것 같다. 사용할 수 있는 상황이 국한되어 있으니깐.
그래도 어렵진 않으니 알아두는 것이 좋은 것 같다.