BFS 기초 이해

BFS는 넓이우선탐색 혹은 레벨탐색이라고 불린다.

root 노드와 가까운 순서(레벨)대로 먼저 탐색하고, 또 탐색한 노드들의 가까운 순서대로 탐색하여 같은 레벨에 있는 모든 노드들부터 탐색하는 방식이다

BFS는 Queue로 구현한다. 그림을 보면서 이해하자.

이렇게 이진트리가 있다고 가정하자.

root가 1이고 레벨이 0이다. 여기서 레벨은 root에서 움직이는 거리, 가까운 거리를 의미한다. root의 레벨은 당연히 0이다. 그렇기에 1을 시작으로 다음 레벨, 가장 가까운 거리에 있는 노드들 2,3을 방문한다. 여기서 방문한 노드들은 큐에넣고, 큐에 있는 순서대로 또 가까운 노드들을 큐에 넣어 레벨 순서대로 진행하는 방식이다

가독성이 떨어질지라도 내가 작성한 그림을 보자

물론 내가 그리긴 했지만 맨 위에 레벨들은 다 -1씩 해줘야한다.

루트인 1을 시작으로 큐에 먼저 넣는다. 그리고 1에 가장 가까운 노드들을 넣고 1을 pop한다.

그러면 큐에 2, 3이 있을거고, 각 노드에 해당하는 가장 가까운 노드들에 넣으면서 넣은 후에는 pop을 한다.

말이 좀 어려운데 나도 이해하기 힘들다.. 코드로 보자

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

class Node {
    int data;
    Node lt, rt;

    public Node(int val) {
        data = val;
        lt = rt = null;
    }
}

public class BfsBasic {
    Node root;

    public static void main(String[] args) {
        BfsBasic tree = new BfsBasic();
        tree.root = new Node(1);
        tree.root.lt = new Node(2);
        tree.root.rt = new Node(3);
        tree.root.lt.lt = new Node(4);
        tree.root.lt.rt = new Node(5);
        tree.root.rt.lt = new Node(6);
        tree.root.rt.rt = new Node(7);
        tree.BFS(tree.root);
    }

    public void BFS(Node root) {
        Queue<Node> Q = new LinkedList<>();
        Q.offer(root);
        int L = 0;
        while (!Q.isEmpty()) {
            int len = Q.size();
            System.out.print(L + " : ");
            for (int i = 0; i < len; i++) {
                Node cur = Q.poll();
                System.out.print(cur.data + " ");
                if (cur.lt != null) {
                    Q.offer(cur.lt);
                }
                if (cur.rt != null) {
                    Q.offer(cur.rt);
                }
            }
            L++;
            System.out.println();
        }
    }
}

처음엔 일일히 다 초기화시켜준다. Node라는 클래스에 root를 넣고, 이 root에 각각 해당하는 lt와 rt를 연쇄적으로 초기화 시킨다. 그 다음 BFS순회할 때, 루트를 넣고 while문을 돌린다.

while문 조건은 큐가 텅텅 빌 때 까지 순회.

처음에 root를 넣었으니 큐에는 root만 존재한다. 큐의 맨 앞의 값을 cur이라는 변수에 담아 빼내고, 이 cur에 있는 lt와 rt를 조사한다. 있으면 넣고 없으면 안넣는다. 이것이 큐의 사이즈(현재는 1)만큼 반복해서 가장 가까운 노드들을 넣어준다는 의미다. 이때 L이라고 표현한 출력문이 있는데, 여기는 레벨을 나타내는 것이다.

그렇게 현재 큐에 가장 가까운 노드들을 넣고, 현재 큐는 빼고, 그러다보면 큐에는 자연스럽게 레벨대로 순회하게 된다

이것이 BFS이다