[묘공단] 너비 우선 탐색(BFS)

깊이 우선 탐색을 봤다면 너비 우선 탐색을 볼 차례다.

 

1. 너비 우선 탐색이란?

깊이 우선 탐색은 시작 노드에서 한 방향으로 끝까지 간 다음에 다른 방향에 대해서도 반복하는 알고리즘이다.

너비 우선 탐색은 이름에서 알 수 있듯이

시작 노드에서 출발해서

인접한 노드를 먼저 탐색하고,

그 다음 인접한 모드들의 인접한 노드들을 탐색하는 방식으로 진행하는 알고리즘이다.

BFS는 큐로 구현되는 경우가 많다.

https://www.geeksforgeeks.org/bfs-vs-dfs-binary-tree/

2. BFS를 굳이 쓰는 이유가 뭘까?

최단 경로.

가중치가 동일한 그래프에서 BFS는, 시작 노드로부터 목표 노드까지의 최단 경로를 보장한다.

 

다른 경우라면

레벨 순서대로 탐색해야 하거나, 특정 깊이에서 모든 노드를 탐색해야 하는 경우에 쓴다.

 

3. BFS는 어떻게 동작하나?

1. 시작 노드를 큐에 추가한다.

* 잠깐 *

트리라는 자료구조를 대상으로 알고리즘을 적용하고 있는데 왜 또 큐를 쓰나요?

그래도 됩니다.

 

트리에서 BFS를 사용할 때 큐를 사용하는 이유는, BFS의 특성과 큐의 동작 방식이 잘 맞기 때문.

BFS에서는 먼저 한 레벨의 모든 노드를 방문한 후, 다음 레벨의 노드들을 방문한다.

이런 순차적인 처리는 큐로 구현하기 좋다.

 

큐를 사용하면 현재 노드의 자식 노드들을 차례로 큐에 추가하고, 큐에서 노드를 꺼내 처리함으로써 

레벨 순서대로 노드를 처리하기에도 좋다.

 

3. BFS의 동작 방법

1. 시작 노드를 큐에 추가한다.

2. 큐에서 노드를 꺼내 처리한다.

3. 해당 노드의 자식 노드를 큐에 추가한다. <- DFS에서는 오른쪽 자식을 스택에 먼저 넣었다면 BFS에서는 왼쪽 자식을 큐에 먼저 넣는다. 차례대로!

4. 큐가 빌 때까지 2번과 3번 과정을 반복한다.

 

4. 코드로 확인합시다!

import java.util.LinkedList;
import java.util.Queue;

class Node {
    int value;
    Node left;
    Node right;

    Node(int value) {
        this.value = value;
        left = null;
        right = null;
    }
}

public class BFSTree {

    public void bfs(Node root) {
        if (root == null) {
            return;
        }

        Queue<Node> queue = new LinkedList<>();
        queue.add(root);

        while (!queue.isEmpty()) {
            Node current = queue.poll();
            System.out.print(current.value + " ");

            // 큐의 특성상 왼쪽 자식을 먼저 넣어야 차례대로 방문됨
            if (current.left != null) {
                queue.add(current.left);
            }

            if (current.right != null) {
                queue.add(current.right);
            }
        }
    }

    public static void main(String[] args) {
        // 간단한 트리 생성
        Node root = new Node(1);
        root.left = new Node(2);
        root.right = new Node(3);
        root.left.left = new Node(4);
        root.left.right = new Node(5);

        // BFS 실행
        BFSTree tree = new BFSTree();
        tree.bfs(root);  // 출력: 1 2 3 4 5
    }
}

       1
      / \
     2   3
    / \
   4   5

 

BFS를 쓰기 좋은 문제는

https://school.programmers.co.kr/learn/courses/30/lessons/1844

프로그래머스

문제 이름에도 '최단거리' 키워드가 있다.

그런데 이 문제는 지금 풀 수가 없어서... 🥲 패스...

 

골든래빗 출판사의 묘공단 스터디를 진행하며

코딩 테스트 합격자 되기 - 자바 편 프로그래머스 제공 97 문제로 완벽 대비를 읽고 정리한 내용입니다.