[알고리즘] BFS

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

BFS란?

루트 노드에서 시작해서 인접한 노드를 먼저 탐색하는 방법입니다.

• 시작 노드로 부터 가까운 노드를 먼저 방문하고 멀리 떨어져 있는 노드를 나중에 방문하는 순회 방법입니다.
• 깊게(Deep)탐색하기 전에 넓게(Wide) 탐색하는 알고리즘입니다.
• 주로 두 노드사이의 최단 경로 혹은 임의의 노드를 찾고 싶을 때 이 방법을 선택합니다.
• 너비 우선 탐색(BFS)이 깊이 우선 탐색(DFS)보다 좀 더 복잡하다.

BFS의 특징

• DFS와 달리 재귀적으로 동작하지 않습니다.
• 그래프 탐색이므로 어떤 노드를 방문했었는지 여부를 반드시 검사해야 합니다.
• 방문한 노드들을 차례로 저장한 후 꺼낼수 있는 자료구조 큐(Queue)를 사용합니다.

문제 예제

        1
      /  \
     2    3
    / \  / \
   4  5 6   7
   
위 와같은 노드가 주어질 경우 7이 저장되어 있는 노드의 Depth를 구하시오

풀이

public class Main7_7 {
    public static void main(String[] args) {
        BinaryTree tree = new BinaryTree();
        int target = 7;
        solution(tree, k);
    }

    public static int solution(BinaryTree tree, int target) {
        int level = 1;
        Queue<Node> queue = new LinkedList<Node>();
        queue.offer(tree.root); // step1
        while(!queue.isEmpty()) {
        	int len = queue.size(); // step2
            for(int i = 0; i < len; i++) { // step3
                Node node = queue.poll();
                if(node.value == target) return level; //step6
                if (node != null) { // step4
                    if(node.left != null) queue.offer(node.left);
                    if(node.right != null) queue.offer(node.right);
                }
                level++; //step5
            }
        }
        return level;
    }
}

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

    public Node(int _value) {
        value = _value;
        left = null;
        right = null;
    }
}

class BinaryTree{
    Node root;

    public BinaryTree(){
        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);
        root.right.left = new Node(6);
        root.right.right = new Node(7);
    }
}

step1 : Queue에 root노드를 넣습니다.
step2 : while문 안에서 queue의 size를 구합니다.
step3 : step2에서 구한 size만큼 for문을 돌립니다. 이때 직접적으로 queue.size()까지 돌린다고 하면 다음 poll, offer하는 과정에서 다음 Depth까지 돌 수 있으니 주의해야 합니다.
step4 : node.left 가 null이 아닌 경우 queue에 node.left를 넣습니다 right도 마찬가지로 null이 아닌경우 queue에 넣습니다.
step5 : 해당 Depth에 있는 노드들을 for문을 통해 모두 탐색했으므로 level(depth)를 1 더해줍니다.
step6 : 해당 Depth를 돌 때 node.value가 target일 경우 바로 level을 반환하여 target의 Depth를 구해줍니다.