[알고리즘/Python] 일반 BFS vs 0-1 BFS(feat. 다익스트라 알고리즘)

 

 

 

 

그래프 탐색에서 최단 경로를 찾을 때 가장 먼저 떠올리는 알고리즘은 BFS(너비 우선 탐색)입니다. 하지만 모든 간선의 가중치가 1이 아니라, 0과 1이 섞여 있는 상황이라면 일반적인 BFS만으로는 효율적인 해결이 어렵습니다. 이때 사용할 수 있는 알고리즘이 0-1 BFS입니다.

 

 

 

---

 

 

1. 일반 BFS (Breadth-First Search)

가장 기본적인 탐색 알고리즘으로, 시작점에서 가까운 노드부터 차례대로 탐색합니다.

• 특징: 모든 간선의 가중치가 동일(보통 1)할 때 사용합니다.
• 자료구조: Queue (Python에서는 collections.deque의 append, popleft 사용)
• 핵심 원리: 큐에 들어간 순서가 곧 시작점으로부터의 거리 순서를 보장합니다.
• 적용 예시: 백준 2178번 미로 탐색

 

 

---

 

2. 0-1 BFS (0-1 Breadth-First Search)

가중치가 0 또는 1로만 구성된 그래프에서 최단 경로(최소 비용)를 찾기 위한 알고리즘입니다.

 

2-1) 왜 0-1 BFS를 사용하는가?

일반 BFS는 큐에 넣는 순서대로 거리가 증가한다고 가정합니다.

하지만 가중치가 0인 간선이 있다면, 나중에 발견된 노드가 먼저 발견된 노드보다 거리가 더 짧을 수 있습니다.

이를 해결하기 위해 Deque(Double-Ended Queue)를 사용합니다.

✦ 핵심 로직
가중치가 0인 경우 ‣ 현재 탐색 레벨과 동일하므로 큐의 맨 앞(appendleft)에 넣습니다. (우선순위 높음)
가중치가 1인 경우 ‣ 다음 탐색 레벨이므로 큐의 맨 뒤(append)에 넣습니다. (우선순위 낮음)

 

 

2-2) 두 알고리즘을 비교해보면

구분	일반 BFS	0-1 BFS
가중치	모두 1 (동일함)	0 또는 1
자료구조	Queue	Deque
삽입 위치	항상 뒤쪽 (append)	0이면 앞쪽, 1이면 뒤쪽
시간 복잡도	O(V + E)	O(V + E)
장점	구현이 단순함	다익스트라(O(E \log V))보다 빠름

 

2-3) 0-1 BFS  예제(백준 2665번. 미로만들기)

이 문제를 풀 때 가장 헷갈리는 점은 "언제 방을 바꿔야 하는가"입니다.

0-1 BFS 관점에서 접근하면 다음과 같은 기준을 세울 수 있습니다.

1. 상태 정의: 각 칸에 도달하기 위해 "검은 방을 바꾼 횟수"를 기록합니다.
2. 이동 규칙:
   • 흰 방(1)으로 갈 때: 비용이 들지 않습니다. (가중치 0) → deque.appendleft()
   • 검은 방(0)으로 갈 때: 방을 하나 바꿔야 하므로 비용이 1 발생합니다. (가중치 1) → deque.append()
3. 방문 조건: 현재 칸을 거쳐 가는 것이 기존에 기록된 최소 파괴 횟수보다 작을 때만 갱신하고 탐색을 이어갑니다.

Tip: 0-1 BFS는 "비용이 0인 경로를 먼저 싹 훑고, 그다음 비용 1인 경로로 넘어간다"는 개념으로 이해하면 쉽습니다

 

✦ 관련 문제 추천

• 백준 1261번: 알고스팟
• 백준 13549번: 숨바꼭질 3

 

---

 

3. 0-1 BFS vs 다익스트라 (Dijkstra)

다익스트라 vs 0-1 BFS

가중치가 있는 그래프에서 최단 경로를 찾는 가장 대표적인 알고리즘은 다익스트라입니다.
하지만 가중치가 0과 1로만 제한된 상황이라면, 다익스트라보다 0-1 BFS가 더 효율적입니다.

 

 

3-1) 작동 방식

• 다익스트라: 모든 간선의 가중치가 양수일 때 사용합니다. 매 순간 거리가 가장 짧은 노드를 찾기 위해 우선순위 큐(Priority Queue)를 사용하며, 이 과정에서 O(log V)의 시간이 소요됩니다.
• 0-1 BFS: 가중치가 0 또는 1인 특수한 상황입니다. Deque을 사용하여 가중치가 0인 노드는 앞에, 1인 노드는 뒤에 넣는 것만으로도 정렬 상태를 유지합니다. O(1)의 시간으로 삽입과 삭제가 가능합니다.

 

3-2) 비교해보면

비교 항목	0-1 BFS	다익스트라 (Dijkstra)
가중치 조건	0 또는 1 (두 종류만 존재)	모든 양수 가중치 ($0 \le w$)
주요 자료구조	Deque	Priority Queue (Heap)
시간 복잡도	O(V + E)	O(E log V) 또는 O(E + V log V)
정렬 과정	필요 없음 (앞/뒤 삽입으로 대체)	매번 최소 거리를 찾기 위해 정렬/힙 재구조화

 

3-3) 왜 0-1 BFS가 더 빠를까?

다익스트라는 우선순위 큐를 유지하기 위해 추가적인 연산(Heapify)이 필요하지만,

0-1 BFS는 큐의 양 끝에 데이터를 넣는 간단한 작업만 수행하기 때문입니다.

따라서 "그냥 지나가는 비용(0)"만 존재하는 문제라면 0-1 BFS를 사용하는 것이 시간 성능 면에서 훨씬 유리합니다.

 

 

 

---