0-1 BFS (0-1 Breadth First Search) 알고리즘

💡 0-1 BFS는 특정 상황의 그래프에서 최단 경로를 찾을 때 사용된다.

 

• 가중치가 0과 1로 이루어진 그래프에서 최단 경로를 찾을 때 사용한다.
• 최단 경로를 구할 때 많이 사용하는 우선순위 큐 다익스트라(Dikjstra) 알고리즘은 시간 복잡도가 O(E log V)인 반면에, 0-1 BFS는 일반적인 BFS 시간 복잡도와 같이 O(V + E)의 선형 시간 복잡도를 갖는다.
• 일반 BFS 에서 큐를 사용하는 것과 달리 덱(Deque)을 사용한다.

 

🚀 0-1 BFS의 동작 과정

1. 덱의 front에서 현재 방문한 노드를 꺼낸다.
2. 연결된 인접 노드를 살펴본다.
3. (현재 비용+ 다음 노드 가중치) < (다음 노드에 기록된 비용)이라면,
   다음 노드에 기록된 비용을 갱신해 준다.
4. 노드가 갱신될 때, 가중치가 0이라면 덱의 front, 가중치가 1이라면 덱의 back에 삽입한다.
5. 덱에 노드가 남지 않을 때까지 위 과정을 반복한다.

 

🚀 시간 복잡도 O(V + E) 이유

노드의 수 : V / 간선의 수 : E

 

모든 정점을 최단 거리로 방문해 1번씩만 방문하므로 덱의 최대 크기는 최대 V이다 : O(V)

 

비용이 적은 경로부터 차례대로 탐색하게 되기 때문에, 모든 간선을 1번씩만 지나가게 된다 : O(E)

 

덱을 사용하며 앞 뒤 정점을 추가하거나 제거할 때 상수 시간이 소요된다 : O(V)

 

상수시간은 시간 복잡도에 영향을 주지 않으므로 0-1 BFS의 시간 복잡도는 O(V + E)이다.

 

 

🚀 0-1 BFS의 핵심코드

백준 1261번 문제의 0-1 BFS 풀이 코드이다.

import java.io.*;
import java.util.ArrayDeque;
import java.util.Deque;
import java.util.StringTokenizer;

public class Main {
    public static void main(String[] args) throws IOException {
        // Input
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        StringTokenizer st = new StringTokenizer(br.readLine());

        int M = Integer.parseInt(st.nextToken());
        int N = Integer.parseInt(st.nextToken());

        int[][] map = new int[N][M]; // 맵 정보

        for (int i = 0; i < N; i++) {

            char[] chars = br.readLine().toCharArray();

            for (int j = 0; j < M; j++) {
                map[i][j] = Character.getNumericValue(chars[j]);
            }
        }

        // 0-1 BFS
        int[] dx = {-1, 0, 1, 0};
        int[] dy = {0, 1, 0, -1};

        Deque<AOJ> dq = new ArrayDeque<>();
        dq.addFirst(new AOJ(0, 0, 0));

        while (!dq.isEmpty()) {
            AOJ aoj = dq.pollFirst();

            if (aoj.row == N - 1 && aoj.col == M - 1) { // Output
                bw.write(Integer.toString(aoj.broken));
                bw.flush();
                break;
            } else {
                for (int i = 0; i < 4; i++) {
                    int r = aoj.row + dx[i];
                    int c = aoj.col + dy[i];
                    if (0 <= r && r < N && 0 <= c && c < M) {
                        if (map[r][c] == 0) {
                            dq.addFirst(new AOJ(r, c, aoj.broken));
                        } else if (map[r][c] == 1) {
                            dq.addLast(new AOJ(r, c, aoj.broken + 1));
                        }
                        map[r][c] = -1; // 방문체크
                    }
                }
            }
        }
    }

    public static class AOJ {
        int row, col, broken;

        public AOJ(int row, int col, int broken) {
            this.row = row;
            this.col = col;
            this.broken = broken;
        }
    }
}

 

🚀 참고

• https://nicotina04.tistory.com/168
• https://lordofkangs.tistory.com/630
• https://velog.io/@idkwhattodo/%EB%84%88%EB%B9%84%EC%9A%B0%EC%84%A0%ED%83%90%EC%83%89-BFS-%EA%B9%8A%EC%9D%B4%EC%9A%B0%EC%84%A0%ED%83%90%EC%83%89-DFS
• https://velog.io/@nmrhtn7898/ps-0-1-BFS

🚀 관련 문제 풀이

• [G4] BOJ_1261 : 알고스팟 (24.05.10)