그래프 탐색 알고리즘 - 너비 우선 탐색 [BFS]

너비 우선 탐색(BFS, Breadth-First Search)

BFS는 그래프 탐색 알고리즘 중 하나로, 시작 노드와 거리가 가장 가까운 노드를 우선하여 방문하는 방식의 알고리즘이다.

 

BFS는 최단 경로를 찾는 알고리즘으로도 많이 쓰이곤 하는데, 시작 노드로부터 직접 간선으로 연결된 모든 노드를 먼저 방문하기 때문이다. 쉽게 말해 문제에 대한 답이 많은 경우 너비 우선 탐색은 이 답 중에서도 가장 가까운 답을 찾을 때 유용하다.

 

BFS는 주로 FIFO(선입선출) 방식인 큐 자료구조를 사용하여 구현한다.

인접한 노드를 반복적으로 큐에 넣도록 알고리즘을 작성하면 자연스럽게 먼저 들어온 것이 먼저 나가게 되어, 가까운 노드부터 탐색을 진행하게 된다.

(DFS는 이와 반대로 스택을 통해 구현한다.) 

---

BFS 작동 원리

1. 탐색 시작 노드를 큐에 삽입하고 방문 처리를 한다.

2. 큐에서 노드를 꺼내 해당 노드의 인접 노드 중에서 방문하지 않은 노드를 모두 큐에 삽입하고 방문 처리를 한다.

3. 2번의 과정을 더 이상 수행할 수 없을 때까지 반복한다.

 

 

BFS의 작동원리를 이해하기 위해 아래 사진을 준비했다.

아래 예제에서는 번호가 낮은 순서부터 처리하도록 구현하는 방법을 사용했다.
(코딩 테스트에서는 명시적으로 낮은 순서부터 처리하도록 문제를 제시하는 경우가 보편적이다.)

Step1 시작 노드인 '1'을 큐에 삽입하고 방문 처리를 한다.

 

Step2 큐에서 노드 '1'을 꺼내고 방문하지 않은 인접 노드를 모두 큐에 삽입하고 방문 처리를 한다.

 

Step3 큐에서 노드 '2'를 꺼내고 방문하지 않은 인접 노드 '7'을 큐에 삽입하고 방문 처리를 한다.

 

Step4 큐에서 노드 '3'을 꺼내고 방문하지 않은 인접 노드 '4'와 '5'를 모두 큐에 삽입하고 방문 처리를 한다.

 

Step5 큐에서 노드 '8'을 꺼내고 방문하지 않은 인접 노드가 없으니 무시한다.

 

Step6 큐에서 노드 '7'을 꺼내고 방문하지 않은 인접 노드 '6'을 큐에 삽입하고 방문 처리를 한다.

 

Step7 남아 있느 노드에 방문하지 않은 인접 노드가 없다.
따라서 모든 노드를 차례대로 꺼내면 최종적으로 다음과 같다.

 

 

방문 순서를 보면 알 수 있듯이 시작 노드와 거리가 먼 순서대로 탐색을 하는 것을 확인할 수 있다. 이러한 작동 원리를 통해 BFS 는 최단 경로를 구하는 알고리즘으로 쓰일 수 있다.

---

BFS 알고리즘 구현 - 자바

BFS는 큐 자료구조에 기초하여 구현하면 되므로 구현이 간단하다.

void BFS(int startIdx) {
    // 시작 정점을 큐에 추가
    Queue<Integer> queue = new LinkedList<>();
    queue.offer(startIdx);

    while (!queue.isEmpty()) {
        int current = queue.poll(); // 큐에서 가장 앞의 정점을 꺼낸다.

        // 현재 정점이 이미 방문된 경우 건너뛴다.
        if (isVisit(current)) {
            continue;
        }

        // 현재 정점 방문 처리
        visit(current);

        // 현재 정점과 인접한 노드들을 큐에 추가 (미방문 노드만)
        for (Node node : linkedNode(current)) {
            if (!isVisit(node)) {
                queue.offer(node.getIdx());
            }
        }
    }
}

 

 

BFS 는 효율적인 운영이 가능하고, 시간/공간 복잡도 면에서 안정적이고, 간선의 비용이 없다면 최단 경로를 구하는 알고리즘으로 쓰일 수 있다는 장점이 있다. (간선의 비용이 있을 경우 다익스트라 알고리즘 등 최단 경로를 구하는 알고리즘을 사용해야 한다.)

 

시간복잡도를 DFS와 비교하자면 DFS는 운이 좋은 경우 시간복잡도가 BFS에 비해 낮고, 최악의 경우 시간복잡도가 BFS에 비해 높다. 하지만 BFS는 순차적으로 노드를 순회하기 때문에 최선의 경우 혹은 최악의 경우 둘 다 안정적인 시간복잡도를 가진다.

---

연습문제 추천

• 백준 - 1260, 2606, 2667, 2178, 7569
• 프로그래머스 - 네트워크, 게임 맵 최단거리, 경주로 건설

출처
- [10분 테코톡] 📚카프카의 탐색 알고리즘
- 이것이 취업을 위한 코딩 테스트다 with 파이썬
- 코딩 테스트 합격자 되기 - 자바 편