설명

말단 노드까지 가장 짧은 경로 구하기

코드

public class ShortNodeBFS {
    public static void main(String[] args) {
        Node 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(4);
        System.out.println(bfs(root));
    }

    public static int bfs(Node root){
        Queue<Node> que = new LinkedList<>();
        que.offer(root);
        int level = 0;

        while(!que.isEmpty()){
            int length = que.size();
            for(int i=0; i<length; i++){
                Node cur = que.poll();
                if(cur.lt == null && cur.rt == null) return level;
                if(cur.lt != null) que.offer(cur.lt);
                if(cur.rt != null) que.offer(cur.rt);
            }
            level++;
        }

        return 0;
    }
}

전 문제에서 DFS로 구했다면 이번엔 BFS로 구하는 방식이다. BFS는 항상 Queue 자료구조를 이용하여 탐색하는 것을 습관화 해야겠다. 이 구조를 BFS 문제를 풀때 바로 떠올리면 문제를 금방 해결할 수 있을텐데... 아직 이 구조가 바로 떠오르지 않는다...

BFS는 Queue를 사용하여 while로 풀어낸다는 구조를 항상 머릿속에 그리자!