[Argorithm] 0-1 BFS

특수한 상황에서 쓰는 0-1 BFS 알고리즘에 대해 알아보자 

📝 0-1 BFS?

0-1 BFS는 가중치가 0 또는 1인 그래프에서 최단 경로를 찾기 위해 사용하는 알고리즘을 말한다.

일반적으로 BFS는 각 이동에서 동일한 가중치를 가지나, 0-1 BFS는 0또는 1의 가중치를 다르게 처리한다.

이 알고리즘은 데크를 이용해서 가중치가 0인 간선을 데크 앞에, 가중치가 1인 간선을 데크 뒤에 추가하는 방식으로 구현한다.

 

특징

• 해당 알고리즘은 문제의 가중치가 0 또는 1로 다르게 처리할 때 사용한다.
• Deque(데크)를 사용하여 구현하며 가중치가 0인 것을 데크 앞에, 가중치가 1인 것을 데크 뒤에 둔다.
• 특수한 상황(가중치가 0, 1)인 상황에서 다익스트라보다 효율적으로 작동한다. 

📝 0-1 BFS 자세히 이해해보기 

현재 노드를 u, 인접한 노드 v로 이동할 때의 가중치를 w라고 하자

• dist[u]는 현재 노드 u까지의 최단 거리이다.
• dist[v]는 인접한 노드 v까지의 최단 거리이다.

이때 우리는 이 dist를 이용해서 가중치에 따라 최단 거리를 다르게 조정해주면 된다.

 

• 가중치가 0인 경우 (w = 0):
  • if dist[v] > dist[u] : dist[v] = dist[u]
• 가중치가 1인 경우 (w = 1):
  • if dist[v] > dist[u]+1 : dist[v] = dist[u]+1

📝 실습해보기 

13549번: 숨바꼭질 3 (acmicpc.net)

0-1 BFS를 연습하기 좋은 문제이다.

import java.io.*;
import java.util.*;

public class Main {
    static int N, K;
    static int[] dist = new int[100001]; // 최단 거리를 저장할 배열

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        N = Integer.parseInt(st.nextToken());
        K = Integer.parseInt(st.nextToken());

        if (N >= K) {
            System.out.println(N - K); // N이 K보다 크거나 같은 경우에는 단순히 걸어가는 것이 최단 시간
        } else {
            bfs();
            System.out.println(dist[K]); // K에 도달하는 최단 시간 출력
        }
    }

    public static void bfs() {
        Deque<Integer> deque = new LinkedList<>();
        Arrays.fill(dist, Integer.MAX_VALUE);
        deque.add(N);
        dist[N] = 0;

        while (!deque.isEmpty()) {
            int current = deque.poll();

            if (current * 2 <= 100000 && dist[current * 2] > dist[current]) {
                dist[current * 2] = dist[current];
                deque.addFirst(current * 2); // 가중치가 0인 경우 덱의 앞에 추가
            }

            if (current + 1 <= 100000 && dist[current + 1] > dist[current] + 1) {
                dist[current + 1] = dist[current] + 1;
                deque.addLast(current + 1); // 가중치가 1인 경우 덱의 뒤에 추가
            }

            if (current - 1 >= 0 && dist[current - 1] > dist[current] + 1) {
                dist[current - 1] = dist[current] + 1;
                deque.addLast(current - 1); // 가중치가 1인 경우 덱의 뒤에 추가
            }
        }
    }
}