트리 - 너비 우선 탐색 알고리즘 (BFS)

너비 우선 탐색 알고리즘 (BFS, Breadth First Search)

 

트리를 조회할 때, 너비를 기반하여 우선적으로 조회한다.

하나의 노드에는 여러 개의 노드가 연결되어 있는데, 특정 노드와 근접한 노드부터 검사한다.

출처 : https://www.freelancinggig.com/blog/2019/02/06/what-is-the-difference-between-bfs-and-dfs-algorithms/

 

트리에는 깊이라는 개념이 있다.

0번 노드는 깊이가 1이며,

1, 2번 노드는 깊이가 2이다.

그 밑으로 3, 4, 5, 6번 노드는 깊이가 3이고, 그 이후는 1씩 추가된다.

 

너비 우선 탐색(BFS)는 깊이 우선 탐색(DFS)과 다르게, 루트 노드에 인접한 노드를 먼저 모두 검사한 후, 그 다음 서브 노드로 옮겨서 그 서브 노드에 인접한 모든 노드를 검사하는 방식으로 동작한다.

 

BFS의 구현은 DFS에서 사용했던 Recursive Call 만을 사용해서는 구현하기 힘들다.

Recursive Call을 아예 사용하지 않는 것은 아니고, 주로 Queue를 사용하는 로직을 Recursive Call을 사용하여 구현할 수 있다.

 

BFS의 진행 상황에 따른 큐 상태를 살펴보자.

 

1. 깊이 1의 루트 노드자신을 검사한다. 큐는 비어있다.

 

2. 루트 노드의 왼쪽 서브 노드(깊이 2)가 비어있지 않다면 왼쪽 서브 노드를 Queue에 넣는다.

 

3. 루트 노드의 오른쪽 서브 노드(깊이 2)가 비어있지 않다면 오른쪽 서브 노드를 Queue에 넣는다.

 

4. queue에서 다음 노드 (가장 오래된 노드, 가장 먼저 나와야 할 노드)를 뽑아낸다.

2, 3번에서 비어있지 않은 경우에 넣은 것이므로, queue가 비어있을 수 있다.

따라서 queue가 비어있지 않는지 체크한 후 queue에서 하나를 뽑아내서 검사(출력)한다.

queue가 비어있다면 순회가 끝난 것으로 종료한다.

 

 

이 과정을 계속해서 반복하면 된다. 이후 과정을 계속 살펴보자.

 

5. 방금 1번 노드(루트 노드의 왼쪽 서브 노드)를 검사했으므로, 1번 노드의 왼쪽 서브 노드인 3번 노드가 존재한다면 queue에 추가한다.

 

6. 방금 1번 노드(루트 노드의 왼쪽 서브 노드)를 검사했으므로, 1번 노드의 오른쪽 서브 노드인 4번 노드가 존재한다면 queue에 추가한다.

 

Queue의 특성 상 먼저 들어간 노드는 루트 노드의 left 서브노드가 들어가게 된다.

또한 Queue는 작업의 순서를 지키며 연산해야 할 때 사용한다.

현재 노드 중 2번 노드가 현재 Queue에 제일 먼저 들어갔으므로,

3, 4 번 노드를 1번 노드 검사 직후 (아직 2번 노드를 검사하지 않은 시점)에 넣는다고 하더라도 이후 Queue에서 하나를 빼는 것은 2번 노드가 나오게 될 것이다.

 

7. Queue에서 하나를 빼서 검사한다.

 

8. 2번 노드의 왼쪽, 오른쪽 서브 노드를 순서대로 Queue에 넣는다.

 

9. Queue에서 하나 빼서 검사한다. 3이 나온다.

 

10. 3의 왼쪽 서브 노드와 오른쪽 서브 노드가 모두 존재하지 않으므로, Queue에 추가하지 않고 다음 탐색으로 넘어간다. 큐의 상태는 그대로 유지된다.

 

11. Queue에서 하나 빼서 검사한다. 4가 나온다.

 

12. 4의 왼쪽 서브 노드와 오른쪽 서브 노드가 모두 존재하지 않으므로, Queue에 추가하지 않고 다음 탐색으로 넘어간다. 큐의 상태는 그대로 유지된다.

 

13. Queue에서 하나 빼서 검사한다. 5가 나온다.

 

14. 5의 왼쪽 서브 노드와 오른쪽 서브 노드가 모두 존재하지 않으므로, Queue에 추가하지 않고 다음 탐색으로 넘어간다. 큐의 상태는 그대로 유지된다.

 

15. Queue에서 하나 빼서 검사한다. 6이 나온다.

 

16. 6의 왼쪽 서브 노드와 오른쪽 서브 노드가 모두 존재하지 않으므로, Queue에 추가하지 않고 다음 탐색으로 넘어간다. 큐의 상태는 그대로 유지된다.

 

17. Queue에서 하나 빼려고 하니 Queue가 비어있다. 따라서 탐색을 종료한다.

 

과정을 잘 살펴보면, 인접한 노드를 바로 검사하는 DFS와 달리, BFS는 Queue라는 별도의 저장공간에 다음에 검사해야 할 순서를 지정하여 저장해놓고, 순서대로 노드를 뽑아서 검사하게 된다.

따라서 트리에서 인덱스 순서대로 검사할 수 있다.

 

 

트리노드는 소스코드로 다음과 같이 정의할 수 있다.

public class TreeNode {
    public int val;
    public TreeNode left;
    public TreeNode right;
    public TreeNode(int x) { val = x; }
}

 

위 트리를 구성하는 소스코드는 다음과 같다.

TreeNode root = new TreeNode(0);
TreeNode left = new TreeNode(1);
TreeNode right = new TreeNode(2);
TreeNode leftleft = new TreeNode(3);
TreeNode leftright = new TreeNode(4);
TreeNode rightleft = new TreeNode(5);
TreeNode rightright = new TreeNode(6);
root.left = left;
root.right = right;
left.left = leftleft;
left.right = leftright;
right.left = rightleft;
right.right = rightright;

 

 

BFS 함수를 소스코드로 표현하면 다음과 같다.

public void bfsSearch(TreeNode currentNode) {
    // 현재 노드가 null이면 순회를 종료한다.
    if (currentNode == null) {
        return;
    }

    // 현재 노드의 값을 출력
    System.out.print(currentNode.val);

    // 현재 노드의 왼쪽이 존재하는 경우 먼저 큐에 넣음
    if (currentNode.left != null)
        queue.add(currentNode.left);

    // 꺼낸 노드의 오른쪽이 존재하는 경우 먼저 큐에 넣음
    if (currentNode.right != null)
        queue.add(currentNode.right);

    // 큐가 비어 있으면 종료
    if (queue.isEmpty()) return;

    // 큐에서 하나 꺼내서 다시 순회 시작
    TreeNode nextNode = queue.poll();
    bfsSearch(nextNode);

}

 

전체 소스코드는 다음과 같다.

/**
 * 너비 우선 순회 BFS (Breadth First Search)
 */
public class BFS {
    static Queue<TreeNode> queue = new LinkedList<>();

    public static void main(String[] args) {
        TreeNode root = new TreeNode(0);
        TreeNode left = new TreeNode(1);
        TreeNode right = new TreeNode(2);
        TreeNode leftleft = new TreeNode(3);
        TreeNode leftright = new TreeNode(4);
        TreeNode rightleft = new TreeNode(5);
        TreeNode rightright = new TreeNode(6);
        root.left = left;
        root.right = right;
        left.left = leftleft;
        left.right = leftright;
        right.left = rightleft;
        right.right = rightright;

        bfsSearch(root);
    }

    public static void bfsSearch(TreeNode currentNode) {
        // 현재 노드가 null이면 순회를 종료한다.
        if (currentNode == null) {
            return;
        }

        // 현재 노드의 값을 출력
        System.out.print(currentNode.val);

        // 현재 노드의 왼쪽이 존재하는 경우 먼저 큐에 넣음
        if (currentNode.left != null)
            queue.add(currentNode.left);

        // 현재 노드의 오른쪽이 존재하는 경우 먼저 큐에 넣음
        if (currentNode.right != null)
            queue.add(currentNode.right);

        // 큐가 비어 있으면 종료
        if (queue.isEmpty()) return;

        // 큐에서 하나 꺼내서 다시 순회 시작
        TreeNode nextNode = queue.poll();
        bfsSearch(nextNode);

    }
}

 

결과는 다음과 같다.

 

대표적인 문제

LeetCode - 107. Binary Tree Level Order Traversal II