양방향 탐색 (Bidirectional Search)

정의

양방향 탐색 (Bidirectional Search) 은 source 와 target 에서 동시에 탐색을 진행하여 중간에서 만나는 전략. 주로 무가중치 그래프의 최단 경로를 BFS 두 개로 찾는 양방향 BFS 형태로 쓰인다.

일반 BFS 의 O(b^d) (b = branching factor, d = depth) 를 O(b^(d/2)) 로 줄인다.

문제 상황과 동기

그래프에서 source 에서 target 까지의 최단 경로를 구해야 한다. 단방향 BFS 는 d 만큼 퍼져나가지만, 양쪽에서 동시에 확장하면 각각 d/2 까지만 확장하면 된다.

• 단방향 BFS: O(b^d). d=10, b=10 이면 10^10 = 100억 노드.
• 양방향 BFS: O(b^(d/2) + b^(d/2)). 같은 조건에서 10^5 + 10^5 = 20만 노드.

핵심 통찰: 탐색 공간은 깊이에 지수적으로 증가한다. 깊이를 절반으로 줄이면 탐색 공간이 제곱근으로 줄어든다.

시각화

핵심 아이디어

invariant: source 에서 출발한 frontier 와 target 에서 출발한 frontier 가 교차하는 순간이 최단 경로.

양방향 BFS:
    q_s = [source], q_t = [target]
    dist_s[source] = 0, dist_t[target] = 0

    while q_s and q_t 모두 비지 않음:
        // 더 작은 frontier 를 확장 (효율 최적화)
        if len(q_s) <= len(q_t):
            expand(q_s, dist_s, dist_t, q_t)
        else:
            expand(q_t, dist_t, dist_s, q_s)

        if 교차 발생: return dist_s[u] + dist_t[u]

알고리즘

bidirectional_bfs(graph, s, t):
    if s == t: return 0

    q_s = [s], q_t = [t]
    ds[s] = 0, dt[t] = 0

    while q_s and q_t:
        // 더 작은 쪽을 확장 (효율)
        if len(q_s) <= len(q_t):
            // q_s 의 모든 노드를 한 레벨 확장
            for u in level of q_s:
                for v in graph[u]:
                    if v in ds: continue
                    ds[v] = ds[u] + 1
                    if v in dt: return ds[v] + dt[v]
                    q_s.push(v)
        else:
            symmetric for q_t

    return -1  // 연결 안 됨

구현

// 양방향 BFS, O(b^(d/2))
#include <bits/stdc++.h>
using namespace std;
​
int bfs(const vector<vector<int>>& g, int s, int t) {
  if (s == t) return 0;
  vector<int> ds(g.size(), -1), dt(g.size(), -1);
  queue<int> qs, qt;
  qs.push(s); ds[s] = 0;
  qt.push(t); dt[t] = 0;
​
  auto expand = [&](queue<int>& q, vector<int>& d_self,
                    vector<int>& d_other) {
      int u = q.front(); q.pop();
      for (int v : g[u]) {
          if (d_self[v] != -1) continue;
          d_self[v] = d_self[u] + 1;
          if (d_other[v] != -1) return v;
          q.push(v);
      }
      return -1;
  };
​
  while (!qs.empty() && !qt.empty()) {
      int meet;
      if (qs.size() <= qt.size())
          meet = expand(qs, ds, dt);
      else
          meet = expand(qt, dt, ds);
      if (meet != -1) return ds[meet] + dt[meet];
  }
  return -1;
}
​
int main() {
  int n, m, s, t;
  cin >> n >> m >> s >> t;
  vector<vector<int>> g(n);
  while (m--) {
      int u, v; cin >> u >> v;
      g[u].push_back(v);
      g[v].push_back(u);
  }
  cout << bfs(g, s, t) << "\n";
}

# 양방향 BFS
from collections import deque
​
def bfs(g, s, t):
  if s == t: return 0
  ds = {s: 0}; dt = {t: 0}
  qs = deque([s]); qt = deque([t])
​
  def expand(q, d_self, d_other):
      u = q.popleft()
      for v in g[u]:
          if v in d_self: continue
          d_self[v] = d_self[u] + 1
          if v in d_other:
              return v
          q.append(v)
      return None
​
  while qs and qt:
      if len(qs) <= len(qt):
          meet = expand(qs, ds, dt)
      else:
          meet = expand(qt, dt, ds)
      if meet is not None:
          return ds[meet] + dt[meet]
  return -1
​
import sys
sys.setrecursionlimit(10**9)
input = sys.stdin.readline
n, m, s, t = map(int, input().split())
g = [[] for _ in range(n)]
for _ in range(m):
  u, v = map(int, input().split())
  g[u].append(v)
  g[v].append(u)
print(bfs(g, s, t))

6 7 0 5
0 1
0 2
1 3
2 3
3 4
4 5
2 5

3

4 2 0 3
0 1
1 2

-1

복잡도

d=10, b=10 기준 단방향 vs 양방향:

변형 / 활용

함정

1. disconnected graph

그래프가 연결되어 있지 않으면 양방향 BFS 도 끝까지 탐색하고 -1 리턴. 이때는 최악의 경우 단방향과 동일한 O(b^d).

2. frontier 크기 균형

항상 더 작은 큐 를 확장해야 효율이 최대. 한쪽이 너무 커지면 사실상 단방향과 다를 바 없음. if qs.size() <= qt.size() 조건 필요.

3. 거리 저장 구조

방문 여부와 거리를 O(1) 에 확인할 수 있어야 함. 배열 또는 dict 사용. Python은 dict가 느릴 수 있으니 방문 배열로 대체 가능.

4. 양방향 탐색 조건

그래프가 무방향 (undirected) 일 때 양방향 BFS 가 가장 자연스럽다. 방향 그래프에서도 가능하지만, target 에서는 incoming edge 로 확장해야 함.

5. 중복 방문 방지

양쪽 모두 visited set 을 유지. 교차 감지는 v in ds and v in dt 로. 각 확장마다 확인.

BOJ 연습 문제

참고

• 너비 우선 탐색
• 다익스트라
• 중간에서 만나기
• A* 알고리즘