0-1 BFS

 0-1 BFS

가중치가 0, 1로 주어진 그래프에서 최단경로를 찾아낼 수 있는 알고리즘

O(V+E)의 시간 복잡도를 가진다.(V : 정점 개수, E : 간선 개수)

 

1. 시간복잡도

O(V+E)의 시간복잡도를 가지는 이유는 무엇일까?

1️⃣ Queue 대신 Deque 사용

0-1 BFS는 Deque(덱) 자료구조를 사용해서 구현한다.

Deque은 Double Ended Queue로 양 방향에서 offer, poll이 가능하다.

• 가중치가 0인 간선으로 이동할 경우, 해당 정점을 덱의 앞부분에 추가한다. 이는 그 정점을 가능한 한 빨리 다시 탐색하기 위해서이다.
• 가중치가 1인 간선으로 이동할 경우, 해당 정점을 덱의 뒷부분에 추가한다. 이는 그 정점을 나중에 탐색하도록 한다.

2️⃣ 한 번씩만 처리되는 정점과 간선

• 정점 처리: 각 정점은 최초로 방문될 때만 덱에 추가된다. 이후에는 이미 방문한 것으로 표시되어 덱에 다시 추가되지 않아서 각 정점은 최대 한 번만 처리된다.
• 간선 처리: 알고리즘 실행 중에 각 간선은 두 정점 사이를 연결하는 데 사용된다. 하지만, 한 번 처리된 간선은 다시 검사할 필요가 없다. 왜냐하면, 최초로 해당 간선을 통해 도달한 정점은 그 시점에서 최단 거리를 보장받기 때문

즉, 0-1 BFS에서는 모든 정점(V)이 최대 한 번씩만 덱에 들어가고 모든 간선도 최대 한 번씩만 검사된다.

따라서 정점(V)수와 간선(E)수에 비례하므로 시간복잡도는 O(V+E)가 된다.

 

2. 다익스트라와 비교

다익스트라도 가중치가 양수인 그래프에서 최단거리를 찾는 알고리즘이다.

01-BFS와 어떤 차이가 있어서 시간복잡도 측면에서 다익스트라가 더 느린걸까?(O(ElogV))

다익스트라는 우선 순위 큐(PriorityQueue)를 사용한다. 즉, 최소 힙을 만드는 연산이 생긴다.

1. 힙에서 꺼낸 노드와 연결된 모든 간선 확인 - 최대 O(E)
2. 조건에 따라 각 간선들을 힙에 넣는 우선 순위 큐의 삽입 연산 - 최대 O(logE)

이때 간선의 숫자는 노드의 제곱보다 작기 때문에

E < V*V
logE < logV*V == 2logV
상수 2 버림
O(logE) = O(logV)
최종 시간복잡도 O(ElogV)

 

3. 0-1 BFS 연산

1. 각 노드를 Deque에 삽입
2. Deque에서 노드를 remove하여 현재 타겟 노드 추출
3. 현재 노드와 연결된 모든 노드 탐색
4. 가중치가 0이면 Deque의 앞에 넣고, 1이면 뒤에 삽입

public static void zeroOneBFS(int source) {
    Deque<Integer> deque = new LinkedList<>();
    deque.offer(source);
    dist[source] = 0;

    while(!deque.isEmpty()) {
        int v = deque.removeFirst();

        for(Node node : graph.get(v)) {
            if(dist[node.vertex] > dist[v] + node.weight) {
                dist[node.vertex] = dist[v] + node.weight;

                if(node.weight == 0) {
                    deque.offerFirst(node.vertex);
                }
                else {
                    deque.offerLast(node.vertex);
                }
            }
        }
    }
}

public static void main(String[] args) {
    int V = 5; // 정점의 수
    dist = new int[V];
    Arrays.fill(dist, INF);

    for (int i = 0; i < V; i++) {
        graph.add(new ArrayList<>());
    }

    // 그래프의 간선 추가

    zeroOneBFS(0); // 0번 정점에서 시작하는 0-1 BFS
}

 

백준의 숨바꼭질 3(13549)에 적용할 수 있다.

 

참고문헌

https://velog.io/@renovatio_hyuns/0-1-BFS