Tree 말단 노드까지의 가장 짧은 경로(BFS)

BFS는 층별로 탐색을 한다. 각 층을 탐색하면서 말단 노드인 것을 확인하면 탐색하던 층을 반환한다. 그래서 DFS보다 최단 거리를 찾는 것에 더 효율적인 것이다.

이전 글에서 설명을 충분히 했다고 여겨서 바로 코드로 구현해볼 것이다.

class Node{
    int data;
    Node lt, rt;
 
    public Node(int root){
        data = root;
        lt = rt = null;
    }
}
 
public class Practice {
    public static Node root;
    public static Queue<Node> q;
 
    public static int BFS(){
        int L=0;
        q.offer(root);
        while(!q.isEmpty()){
            int len = q.size();
            for(int i=0; i<len; i++){
                Node cur = q.poll();
                if(cur.lt == null && cur.rt == null) return L;
                if(cur.lt != null) q.offer(cur.lt);
                if(cur.rt != null) q.offer(cur.rt);
            }
            L++;
        }
        return -1;
    }
 
    public static void main(String[] args){
        q = new LinkedList<>();
        root = new Node(1);
        root.lt = new Node(2);
        root.rt = new Node(3);
        root.lt.lt = new Node(4);
        root.lt.rt = new Node(5);
 
        q.offer(root);
        System.out.println(BFS());
    }
}