[Algorithm] 0-1 BFS 알고리즘 with JAVA

0-1 너비 우선 탐색

 

들어가며

이번 글은 그래프 탐색에 관한 글로 읽기 전에 아래의 링크에서 그래프 이론을 숙지하고, 너비 우선 탐색 및 데이크스트라 알고리즘을 먼저 익히고 나면 정말 쉽게 배울 수 있습니다.

[Algorithm] 그래프 이론 및 그래프 탐색

[Algorithm] BFS 알고리즘 with JAVA

[Algorithm] Dijkstra 알고리즘 with JAVA

 

---

 

0-1 BFS : 0-1 Breadth First Search

1. 알고리즘 명칭

0-1 너비 우선 탐색이란 알고리즘의 명칭은 그래프를 너비 우선 방식으로 탐색하지만 간선에 0 또는 1의 가중치가 존재하는 경우입니다.

 

2. 목적

0-1 너비 우선 탐색은 한 정점에서 출발해 간선에 가중치가 0 또는 1만 존재하는 그래프에서 최소 비용을 구하는 것이 목적입니다. 일반적인 BFS와 데이크스트라의 사이의 단계라고 생각하면 쉽습니다. 양의 가중치가 존재하므로 데이크스트라의 한 영역이지만 가중치가 0 또는 1이기 때문에 BFS와는 살짝 다릅니다. 

 

3. 특징

1. 간선의 가중치는 반드시 0 또는 1이어야 함

2. Deque 자료구조를 사용함

3. 시간 복잡도는 O(V + E)

3. 0-1 BFS 문제는 데이크스트라로도 해결 가능

4. 탐색 시 각 노드마다 최소 비용을 저장할 int 배열 필요

 

 

그림으로 보는 0-1 BFS

0-1 BFS는 BFS와 데이크스트라 알고리즘을 이미 알고 있다면 정말 쉬운 알고리즘입니다. 본격적으로 설명하기에 앞서 아래 GIF를 통해 0-1 BFS의 동작 과정을 대략적으로 이해할 수 있습니다.

0-1 BFS GIF

 

검정색 간선이 가중치가 0이고 녹색 간선은 가중치가 1인 그래프입니다. 1번 노드부터 시작해 가중치가 0인 노드 위주로 탐색하는 것을 볼 수 있습니다.

 

0-1 BFS 알고리즘은 Deque 자료구조를 사용한다고 했습니다. 또한, 방문 배열이 필요합니다. 따라서 Deque 객체 deq과 방문 배열 boolean visit[]을 선언해야합니다.

 

1. 비용 배열 ∞으로 저장 및 1번 노드부터 그래프 탐색

0-1 BFS 이해를 돕기 위해 GIF에서 봤던 그래프에서 가중치가 1인 간선을 더 추가해 동작 과정을 설명하겠습니다.

 

다른 그래프 탐색 알고리즘과 마찬가지로 처음 노드를 삽입하면서 시작합니다. 0-1 BFS에서 사용하는 자료구조는 Deque입니다.

 

그리고 탐색을 시작하기 전 각 노드를 이동하는 비용은 모두 ∞이므로 ∞으로 초기화해줍니다.

 

2. 덱에서 노드 꺼내서 인접 노드 탐색

 

1번 노드와 인접한 노드는 2, 3, 4, 6번 노드입니다. 하지만 2, 3번은 가중치가 0이고 4, 6번은 가중치가 1이므로 2, 3번은 덱의 앞쪽에 위치해야하고 4, 6번은 덱의 뒤쪽에 위치해야합니다. 데이크스트라에서 비용을 기준으로 우선순위 큐에 저장했던 것과 같은 원리입니다.

 

각 가중치에 따라 덱에 삽입한 모습은 위의 그림과 같습니다.

 

또한, 덱에 노드를 삽입하면서 cost 배열도 갱신해줍니다.

 

3. 덱에서 2번 노드를 꺼내어 인접 노드 탐색

 

2번 노드를 추출했을 때 인접한 노드는 5번 노드 밖에 없습니다. 5번 노드로 이동하는 최소 비용은 무한대였으므로 2번 노드에서 5번 노드로 0의 비용으로 이동할 수 있게 됩니다. 가중치가 0이니 덱의 앞쪽에 삽입합니다.

 

4. 덱에서 5번 노드를 꺼내어 인접 노드 탐색

 

5번 노드를 추출했습니다. 5번 노드는 3, 7, 8번 노드와 인접했습니다. 3번 노드로 이동하는 최소 비용은 현재 0이므로 굳이 덱에 추가할 필요가 없습니다. 7, 8번 노드는 무한대이므로 덱에 추가하고 cost 배열의 비용을 1로 갱신합니다.

 

5. 덱에서 3번 노드를 꺼내어 인접 노드 탐색

 

3번 노드를 추출했습니다. 3번 노드에서 4, 5번 노드로 이동할 수 있는데 5번 노드로 이동하는 최소 비용은 이미 0이므로 덱에 추가할 필요가 없습니다. 하지만 4번 노드로 이동하는 최소 비용은 현재 1이고, 간선의 가중치가 0이므로 0의 비용으로 4번 노드로 이동할 수 있게 됩니다.

 

6. 덱에서 4번 노드를 꺼내어 인접 노드 탐색

 

4번 노드를 추출했습니다. 9번 노드로 이동하는 최소 비용이 무한대이므로 9번 노드를 덱에 추가합니다. 이때 간선의 가중치가 1이므로 덱의 뒤쪽으로 삽입합니다. 마지막으로 비용 배열을 1로 갱신합니다.

 

7. 덱에서 남은 노드는 전부 추출

 

현재부터 덱에 남은 모든 노드도 위처럼 동일한 과정을 거치지만 전부 비용이 같거나 높은 이유로 더이상 덱에 삽입이 일어나지 않습니다. 결과적으로 위의 그래프가 0-1 BFS의 결과인 것을 알 수 있습니다.

 

 

예제의 그래프를 최소 비용의 관점으로 그래프를 추상화한다면 간선의 가중치가 0인 노드끼리는 전부 합친 것과 같습니다. 아래의 그림 참고 바랍니다.

 

 

0-1 BFS 실제 구현 코드 : 일반 그래프

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayDeque;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Deque;
import java.util.List;
import java.util.StringTokenizer;

public class Main_01BFS {
    static final int INF = 100000000;

    static int node, edge;
    static List<List<int[]>> list = new ArrayList<>(); // 인접 리스트
    static int[] cost;

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        // 노드, 간선 수 입력
        StringTokenizer st = new StringTokenizer(br.readLine(), " ");
        node = Integer.parseInt(st.nextToken());
        edge = Integer.parseInt(st.nextToken());

        // 인접 리스트 초기화
        for(int i = 0; i <= node; i++) {
            list.add(new ArrayList<>());
        }

        for(int i = 0; i < edge; i++) {
            st = new StringTokenizer(br.readLine(), " ");
            int start = Integer.parseInt(st.nextToken());
            int end = Integer.parseInt(st.nextToken());
            int c = Integer.parseInt(st.nextToken());

            // 인접 리스트 정보 저장
            list.get(start).add(new int[] {end, c});
            list.get(end).add(new int[] {start, c});
        }

        // 0-1 너비 우선 탐색 메서드 호출
        // 1번 노드에서 출발해 각 노드로 이동하는 최소 비용을 구함
        bfs(1);

        // 1번 노드에서 각 노드로 이동하는 최소 비용 출력
        for(int i = 1; i <= node; i++) {
            System.out.println(1+" >> "+i+" : "+cost[i]);
        }
    }

    private static void bfs(int i) {
        // 덱 자료구조 사용
        Deque<int[]> deq = new ArrayDeque<>();
        // 최소 비용 저장할 배열 초기화
        cost = new int[node+1];
        Arrays.fill(cost, INF);

        // 덱에 시작 노드 추가
        // 시작 노드로 이동하는 비용은 0이므로 두번째 인덱스에 0 저장
        deq.offerFirst(new int[] {i, 0});
        // 노드 시작지점의 최소 비용은 0
        cost[i] = 0;

        while(!deq.isEmpty()) {
            // 덱의 앞에서 노드 추출
            int[] poll = deq.pollFirst();

            for(int[] out : list.get(poll[0])) {
                // 추출한 노드에서 인접 노드로 가는 비용
                // 현재에 0 또는 1이 더해짐
                int c = poll[1] + out[1];

                // 계산한 비용 c가 최소 비용 배열에 저장된 값보다 작은 경우만 덱에 추가
                if(cost[out[0]] > c) {
                    if(out[1] == 0) { // 가중치가 0이라면 덱의 앞쪽에 삽입
                        deq.offerFirst(new int[] {out[0], c});
                    } else { // 가중치가 1이라면 덱의 뒤쪽에 삽입
                        deq.offerLast(new int[] {out[0], c});
                    }
                    cost[out[0]] = c;
                }
            }
        }
    }
}

입력
9 14
1 2 0
1 3 0
1 4 1
1 6 1
2 5 0
3 4 0
3 5 1
3 6 1
4 9 1
5 7 1
5 8 1
6 7 1
6 9 0
7 8 0

출력
1 >> 1 : 0
1 >> 2 : 0
1 >> 3 : 0
1 >> 4 : 0
1 >> 5 : 0
1 >> 6 : 1
1 >> 7 : 1
1 >> 8 : 1
1 >> 9 : 1

 

 

0-1 BFS와 Dijkstra의 실행 시간 차이

0-1 BFS : 0.201 ms
Dijkstra : 6.580 ms

 

제 노트북 기준으로 9개의 노드를 탐색하는데 평균적으로 6ms의 차이가 났습니다. 6ms 차이라고 생각하면 작지만 30배라는 점을 고려하면 완전 크게 느껴지는 것을 알 수 있습니다. 따라서 가중치가 0 또는 1이라면 0-1 BFS 사용하는 것을 적극 권장합니다.

 

 

.

.

.

 

마치며

마지막으로 0-1 BFS 알고리즘을 연습할 수 있는 문제를 추천드립니다. 사실 0-1 BFS의 꽃은 격자 그래프인데 시간나면 추가로 작성해보겠습니다..ㅎㅎ

• 2665 미로 만들기 : https://www.acmicpc.net/problem/2665
• 1261 알고스팟 : https://www.acmicpc.net/problem/1261 (미로 만들기와 유사)
• 23563 벽 타기 : https://www.acmicpc.net/problem/23563

그래프 탐색 알고리즘 벌써 5번째 작성했습니다. 그래프 알고리즘 포스팅하는 동안 계속 그래프 문제만 풀고 있는데 문제가 다양해서 갈수록 재밌어지네요! 😊

다음은 벨만 포드 알고리즘에 대해 다뤄보겠습니다.

 

궁금한 점이나 피드백은 댓글로 부탁드립니다.