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

이 게시글에서는 특정한 상황에 놓인 그래프에서 최단 경로를 찾을 때 $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

13549번: 숨바꼭질 3

 

수빈이가 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 <bits/stdc++.h>

using namespace std;
using ll = long long;
using pii = pair<int, int>;

int dist[222222];
int n, k;

void solve()
{
  cin >> n >> k;
  deque<int> 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

2423번: 전구를 켜라

 

이런 거라던지 - 풀이

 

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

E - Stronger Takahashi

 

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

 

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

 

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