[스터디/알고리즘] BFS

시작하며

저번 주는 DFS였다면 BFS가 안 나오면 섭하다. 둘 다 그래프 탐색의 방법이지만 확실한 구현 방법과 용도의 차이가 있는 만큼 정리해 볼 필요가 있다고 생각한다.

BFS(Breadth First Search)

BFS(Breadth First Search, 너비 우선 탐색) 는 DFS와 마찬가지로 그래프 탐색 방법 중 하나이다. 최대한 깊숙히 들어가서 노드를 방문하던 DFS와 달리 인접한 노드들을 우선해서 방문하며, 그렇게 전체를 방문할 수 있도록 넓게(너비를 우선으로) 뻗어나가며 탐색한다. 이를 위해 큐 자료구조를 이용하며, 자세한 과정은 다음과 같다.

1. 탐색을 시작하는 노드(시작점)을 큐에 삽입(enqueue) 하고 방문 처리한다.
2. 큐에서 노드를 꺼내(dequeue), 해당 노드 중에 방문 처리하지 않은 노드들을 전부 큐에 삽입하고 방문 처리한다.
3. 이 과정을 모두 끝날 때 까지 반복한다.

각각을 활용하여 해결할 수 있는 문제의 유형도 많이 다르다.
문제를 해결했던 경험 상으로는, 여러 개의 각각의 그래프가 나뉘어져 있으면 DFS를 사용했고(막힌 곳 까지 먼저 갔다 돌아와야 나뉘어진 그래프의 개수를 파악하기 더 쉽다), 미로에서 탈출하는 유형의 문제에선 미로를 그래프로 표현해 BFS를 이용했었다. 미로를 탈출하려면 도착점까지 모든 경우를 생각하여 도달해야 하기 때문이라고 생각하면서 문제를 해결했던 기억이 난다.

구현 예시

DFS에서 이용했던 그래프와 같은 그래프를 가져왔다. (결과의 차이를 비교하기 쉽게 하기 위함이다)

BFS를 수행하는 Java 코드와 결과는 다음과 같다.

코드

package algorithm;

import java.util.ArrayDeque;
import java.util.HashMap;
import java.util.List;

public class GraphSearch {

  static void initGraph(HashMap<Integer, List<Integer>> graph) {
    for(int i=1; i<=8; i++) {
      graph.put(i, List.of());
    }

    graph.put(1, List.of(2, 3, 4));
    graph.put(2, List.of(7));
    graph.put(4, List.of(5, 6));
    graph.put(5, List.of(6));
    graph.put(7, List.of(8));
  }

  static void BFS(int start, HashMap<Integer, List<Integer>> graph,
      boolean[] visited) {
    ArrayDeque<Integer> queue = new ArrayDeque<>();
    visited[start] = true;
    queue.add(start);

    while (!queue.isEmpty()) {
      int current = queue.pollFirst();
      System.out.print(current + " ");

      for (int v: graph.get(current)) {
        if (!visited[v]) {
          queue.add(v);
          visited[v] = true;
        }
      }
    }
  }

  public static void main(String[] args) {
    HashMap<Integer, List<Integer>> graph = new HashMap<>();
    boolean[] visited = new boolean[9];

    initGraph(graph);
    BFS(1, graph, visited);
  }
}

결과

1 2 3 4 7 5 6 8