0-1 BFS는 가중치가 0과 1로만 이루어진 그래프 상에서 최단거리를 찾는 알고리즘입니다.

왜 0-1 인가?

BFS는 가중치가 없는 그래프에서 최단거리를 찾을 수 있는 알고리즘입니다.
가중치가 있는 그래프에서의 최단거리는 다익스트라 알고리즘을 통해서 구할 수 있습니다.

• BFS는 큐를 사용하여 현재 노드에서 연결된 노드를 목표로 탐색을 하기 때문에 가중치가 있는 그래프에서는 사용하기 어렵습니다. (가중치가 있을 경우 더 멀리 연결되어 있는 노드와의 거리가 더 가까울 수 있기 때문입니다.)
• 다익스트라 알고리즘에서는 최소힙을 사용하여 가장 가까운 거리를 가진 노드를 목표로 탐색하기 때문에 가중치가 있어도 최단거리를 찾아갈 수 있습니다.

  정리하면 다익스트라는 그리디 하지만 BFS는 그리디하지 않기에, 가중치가 있는 그래프의 경우 BFS를 쓸 수 없다고 설명할 수 있습니다.

그러나 가중치가 0 또는 1만 존재할 경우는 특수한 경우로써 BFS로 최단경로를 구할 수 있습니다.
일반 큐 대신 양방향 큐를 사용하여 가중치가 0인 노드는 앞부분에 삽입, 1인 노드는 뒷부분에 삽입함으로써 가장 가까운 노드부터 BFS탐색을 할 수 있기 때문입니다.

0-1 BFS를 써야하는 이유

이유는 딱 하나 '빠르다'

다익스트라를 쓰던, 0-1 BFS를 쓰던 문제는 똑같이 풀립니다. 그러나 특수조건에서만 사용할 수 있는 0-1 BFS를 굳이 쓰는 이유는 딱 하나, '빠르기 때문'입니다.

아래의 조건에서 시간복잡도를 계산해보겠습니다.

• V: 노드의 숫자
• E: 간선의 숫자

다익스트라 알고리즘 시간복잡도

알고리즘은 아래와 같은 과정을 반복합니다.

1. 힙에서 꺼낸 노드와 연결된 모든 간선 확인 - 최대 O(E)
2. 조건에 따라 각 간선들을 힙에 넣음 - 최대 O(logE)

시간복잡도는 최악의 상황을 기준으로 계산하기 때문에 둘의 과정을 고려했을 때 O(ElogE)가 됩니다.
항상 간선의 숫자는 노드의 갯수 제곱보다 작기 때문에 $E<V^2$가 성립하고 $logE < logV^2 = 2logV$ 이므로 시간복잡도 계산방식에 의해 상수 2를 버리고 O(logE) = O(logV)로 나타낼 수 있습니다.
최종 시간복잡도 : O(ElogV)

0-1 BFS 알고리즘 시간복잡도

BFS 탐색은 최단거리를 찾기 전까지 모든 노드를 한 번씩 방문하기 때문에 기본적으로 선형탐색입니다.
아래와 같은 과정을 반복합니다.

1. 각 노드를 deque에 삽입 - 최대 O(V)
2. deque에서 노드를 pop 하여 현재 노드로 대입 - O(1)
3. 현재 노드와 연결된 모든 노드 탐색 - 최대 O(E)
4. 3번의 각 탐색에 대하여 deque에 삽입 - 최대 O(1)

Pseudo code

visited = [False] * V
deque.appendleft(0, root)

while deque:
    cost, current_node = deque.popleft()
    visited[current_node] = True
    for node in graph[current_node]:
    	if not visited[node]:
    		if cost of current_node to node == 0:
        		deque.appendleft((cost, node))
        	elif cost of current_node to node == 1:
        		deque.append((cost + 1, node))

의사코드와 알고리즘에서의 시간복잡도를 종합해보면, 각 노드에 대하여 2, 3, 4번 과정을 반복하므로

$O(V) * \{ O(1) + O(E) + O(1)\} \newline = O(V) + O(V * E) + O(V) \newline = O(2V) + O(E) \newline = O(V) + O(E) \newline = O(V + E)$

위에서 O(V*E)가 O(E)로 치환되는 이유는 "(V * E) 는 전체 간선의 개수와 같아서" 라는데.....
🤔음...... 이 말의 뜻을 잘 모르겠다.
아시는 분이 계시다면 댓글로 설명해주시면 감사할것 같습니다. 🤔
그러나 0-1 BFS의 시간복잡도 또한 선형탐색을 따르므로 일반적인 DFS, BFS와 동일한 O(V+E) 라는것.

다익스트라 알고리즘보다 훨씬 훨씬 빠른 속도이기 때문에 문제에서 가중치 0, 1만 보인다면 바로 0-1 BFS로 참교육을 해주자.

적용해볼만한 백준 문제

👉 숨바꼭질 3

문제가 굉장히 심플하게 기술되어있지만, 평면좌표가 아닌 1차원 좌표기 때문에 그래프 알고리즘을 떠올리기가 쉽지 않을 수도 있습니다.
가장 빠른 수단을 찾는다는 점에서 다익스트라를 채용할 수 있지만, 가중치가 0, 1로만 이루어져 있다는 것을 캐치한다면 0-1 BFS로 굉장히 빠르게 혼내줄 수 있습니다.

두 방법 모두 파이썬 코드로 구현하면 아래와 같습니다.

"""
Dijkstra 풀이
"""

import heapq
import sys

N, K = map(int, sys.stdin.readline().split())
visited = [False] * 100001

heap = []
heapq.heappush(heap, (0, N))
while heap:
    time, now = heapq.heappop(heap)
    if now > 100000:
        continue
    visited[now] = True
    if now == K:
        print(time)
        break
    temp = now << 1
    if temp <= 100000 and not visited[now << 1]:
        heapq.heappush(heap, (time, now << 1))
    if now + 1 <= 100000 and not visited[now + 1]:
        heapq.heappush(heap, (time + 1, now + 1))
    if now - 1 >= 0 and not visited[now - 1]:
        heapq.heappush(heap, (time + 1, now - 1))

"""
0-1 BFS 풀이
"""

import sys
from collections import deque

N, K = map(int, sys.stdin.readline().split())
visited = [False] * 100001

d = deque()
d.appendleft((0, N))

while d:
    time, now = d.popleft()
    visited[now] = True
    if now == K:
        print(time)
        break
    if (now << 1) <= 100000 and not visited[now << 1]:
        d.appendleft((time, now << 1))
    if now + 1 <= 100000 and not visited[now + 1]:
        d.append((time + 1, now + 1))
    if now - 1 >= 0 and not visited[now - 1]:
        d.append((time + 1, now - 1))

결과는....?!