[알고리즘] 7-9 Tree 말단 노드까지의 가장 짧은 경로 - BFS(넓이우선탐색)(인프런 자바(Java) 알고리즘 문제풀이 : 코딩테스트 대비 강의)

인프런의 자바(Java) 알고리즘 문제풀이 : 코딩테스트 대비 강의를 수강하며 풀이를 정리하고 있습니다.

• 문제 설명 : 주어진 이진트리의 루트 노드1에서 말단 노드까지의 길이 중 가장 짧은 길이(간선의 개수가 적은)를 구하는 문제

풀이

• 넓이우선탐색(BFS)을 진행하다가 자식이 없는 말단 노드를 만나면 해당 노드의 레벨을 반환한다.

package inflearn.recursive_tree_graph;

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

//Tree 말단 노드까지의 가장 짧은 경로
public class Main7_9 {

    public static int bfs(Node root) {
        Queue<Node> q = new LinkedList<>();
        q.offer(root);
        int level = 0; //트리의 현재 레벨 = 간선의 개수

        while (!q.isEmpty()) {
            int len = q.size();

            for (int i = 0; i < len; i++) {
                Node node = q.poll();

                //자식노드가 없다는건 말단 노드
                if (node.left == null && node.right == null) 
                    return level;

                if (node.left != null)
                    q.offer(node.left);

                if (node.right != null)
                    q.offer(node.right);
            }

            level++;
        }

        return -1;
    }

    public static void main(String[] args) {
        Node root = new Node(1);

        root.left = new Node(2);
        root.left.left = new Node(4);
        root.left.right = new Node(5);

        root.right = new Node(3);

        System.out.println(bfs(root));
    }
}