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

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

728x90

이 게시글에서는 특정한 상황에 놓인 그래프에서 최단 경로를 찾을 때 $O(V + E)$의 시간 복잡도로 해결할 수 있는 0-1 BFS에 대해 다룬다.

거기! 혹시 코테를 준비하신다면?

딱 말할 수 있다. 0-1 BFS를 공부할 것을 강력히 권한다.

본인은 어떤 기업의 코딩 테스트에서 0-1 BFS를 사용할 수 있는 문제를 목격한 뒤로 이 글을 쓰기로 마음먹었기 때문이다.

문제에 비공개 조약이 걸려 있으므로 어떤 기업인지 자세히 말할 수 없지만 전통적인 대기업의 계열사이다.

따라서 대회에 초점을 맞춘 사람이 아니어도 0-1 BFS를 공부해서 손해를 볼 일은 없을 것이다.

0-1 BFS란?

BFS는 BFS인데 특수한 환경에서 작동할 수 있는 BFS이다. 그 특수한 환경이 뭐냐고?

0-1에 생각하면 무엇인지 추측할 수 있다. 0-1 BFS는 가중치가 0과 1로만 주어진 그래프에서 최단 경로를 찾고자 할 때 BFS를 응용하여 풀 수 있게 된다.

아니 최단 경로는 다익스트라가 베스트가 아니란 말인가? 적어도 이 그래프에서는 아니다.

보편적으로 사용하는 다익스트라 알고리즘의 시간 복잡도가 $O(E \log E)$ 혹은 $O(E \log V)$인데 0-1 BFS를 사용하면 단지 $O(V + E)$의 선형 시간 복잡도로 문제를 해결할 수 있기 때문이다.

0-1 BFS의 동작

왜 0-1 BFS가 $O(V + E)$에 동작할 수 있을까?

이는 BFS에서 노드를 관리하기 위해 큐를 사용하는 대신 덱(deque)을 사용하여 실현할 수 있다.

0-1 BFS는 다음 과정에 따라 최단 경로를 찾게 된다.

1. 덱의 front에서 현재 노드를 꺼낸다.

2. 연결된 인접 노드를 살펴본다.

3. 현재 노드까지 소비된 비용 + 그 노드를 향하는 가중치 < 그 노드까지 가는데 소비된 비용이면 소비된 비용을 갱신해준다.

4. 노드가 갱신된 상태에서 만약 그 노드를 향하는 가중치가 0이면 덱의 front, 1이면 덱의 back에 삽입하도록 한다.

5. 덱에서 더 이상 꺼낼 노드가 없을 때까지 위 과정을 반복한다.

$O(V + E)$ 증명

위 과정을 생각해보자.

0-1 BFS를 수행하면 가중치가 1인 간선을 0번 거쳐간 노드 -> 가중치가 1인 간선을 1번 거쳐간 노드 -> .... -> 가중치가 1인 간선을 E번 거쳐간 노드

이런 식으로 비용이 적은 경로부터 탐색을 하게 되기 때문에 특정 간선을 2번 이상 지나가는 경우는 없다. $O(E)$

똑같이 모든 정점도 2번 이상 경유하는 경우가 없으므로 덱 크기는 최대 $|V|$이다. $O(V)$

따라서 0-1 BFS는 $O(V) + O(E) = O(V + E)$의 시간 복잡도를 가지게 된다.

0-1 BFS 문제 풀어보기

백준 온라인 저지에서 0-1 BFS의 입문 문제인 숨바꼭질 3을 풀어보자.

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

수빈이가 0초의 비용으로 이동하는 경우와 1초의 비용으로 이동하는 경우가 주어진다.

주어진 상황을 0-1 BFS로 탐색하면 최단 경로(가장 빠른 시간)를 구할 수 있게 된다.

다만 2배의 위치로 N의 제한을 넘어 이동했을 때 최적해를 가질 수 있다는 점을 유의하여 이동할 수 있는 노드는 넉넉히 20만 개 이상으로 설정해야 한다.

위치에 대해 조심하면서 구현하면 0ms로 정답을 받을 수 있다.

다음은 정답 코드이다.

#pragma GCC target("avx,avx2,fma") #pragma GCC optimize("Ofast") #pragma GCC optimize("unroll-loops") #include using namespace std; using ll = long long; using pii = pair; int dist[222222]; int n, k; void solve() { cin >> n >> k; deque dq; dq.push_back(n); fill(dist, dist + 222222, 1e9); dist[n] = 0; while (dq.size()) { int cur = dq.front(); dq.pop_front(); if (cur == k) { cout << dist[k]; return; } int warp = cur * 2; if (warp <= 200000 && dist[warp] > dist[cur]) { dist[warp] = dist[cur]; dq.push_front(warp); } int l = cur - 1, r = cur + 1; if (l >= 0 && dist[l] > dist[cur] + 1) { dq.push_back(l); dist[l] = dist[cur] + 1; } if (r <= 200000 && dist[r] > dist[cur] + 1) { dq.push_back(r); dist[r] = dist[cur] + 1; } } } int main() { cin.tie(nullptr); ios::sync_with_stdio(false); solve(); }

0-1 BFS로 어려운 문제를 낸다고 하면 보통 성가신 구현을 하는 경우가 많다.

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

이런 거라던지 - 풀이

https://atcoder.jp/contests/abc213/tasks/abc213_e

이런 문제같이 0-1 BFS의 사용이 핵심인 문제는 개념이 그렇게 어려운 것이 아니기 때문에 귀찮은 구현을 동반하게 된다. 그 코딩 테스트에서도 제법 성가시게 나왔었다.

하지만 적지 않은 연습 문제를 백준 온라인 저지에서 풀어볼 수 있으니 충분한 연습을 할 수 있을 것이다.

지금까지 0-1 BFS에 대해 알아보았다. 앞으로 가중치가 0과 1만 있는 최단 경로 문제를 보게 되면 바로 0-1 BFS로 참 교육을 해주자.

728x90

from http://nicotina04.tistory.com/168 by ccl(A) rewrite - 2021-09-20 20:27:04