Tree에서 말단노드까지의 경로(BFS)

01 May 2023 in Algorithm on Java, Coding, Test

문제

아래 그림과 같은 이진트리에서 루트 노드 1에서 말단노드까지의 길이 중 가장 짧은 길이를 구하는 프로그램을 작성하세요. 각 경로의 길이는 루트노드에서 말단노드까지 가는데 이동하는 횟수를 즉 간선(에지)의 개수를 길이로 하겠습니다.

가장 짧은 길이는 3번 노드까지의 길이인 1이다.

해결방법

• BFS는 Queue에 노드를 저장하고 Queue가 empty 일 때까지 반복하면서 넣고/빼고를 수행한다.

코드

import java.util.*;

class Node {
    int data;
    Node lt, rt;

    public Node(int val) {
        data = val;
        lt = rt = null;
    }
}

public class Main {
    Node root;

    public int BFS(Node root) {
        Queue<Node> Q = new LinkedList<>();
        // 큐에 루트노드 넣고 시작한다.
        Q.offer(root);
        int L = 0;
        // 큐가 빌 때까지 반복.
        while (!Q.isEmpty()) {
            int len = Q.size();
            // 큐 사이즈 만큼 반복.
            for (int i = 0; i < len; i++) {
                // 큐에서 노드를 꺼낸다.
                Node cur = Q.poll();
                // 1개라도 없으면 말단노드 이므로 리턴한다.
                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 0;
    }

    public static void main(String args[]) {
        Main.Main tree = new Main.Main();
        // 트리 구조 생성
        tree.root = new Node(1);
        tree.root.lt = new Node(2);
        tree.root.rt = new Node(3);
        tree.root.lt.lt = new Node(4);
        tree.root.lt.rt = new Node(5);
        System.out.println(tree.BFS(tree.root));
    }
}