[JAVA] 알고리즘 : Tree 말단노드까지 가장 짧은 경로(DFS/BFS)

 

 

 

그림과 같은 이진트리에서 루트 노드 1에서 말단노드까지의 길이 중 가장 짧은 길이를 구하는 프로그램을 작성하라.

각 경로의 길이는 루트노드에서 말단노드까지 가는데 이동하는 횟수를, 즉 간선(에지)의 개수의 길이이다. 

 

 

 

DFS

class Node{
    int data;
    Node lt, rt;
    public Node(int val){
        data=val;
        lt=rt=null;
    }
}
public class Main{
    Node root;
    public int DFS(int L, Node root){
        if(root.lt==null && root.rt==null) return L; // 말단 노드라면 레벨 리턴
        else return Math.min(DFS(L+1, root.lt), DFS(L+1, root.rt)); // 자식 노드들의 최솟값 리턴
    }

    public static void main(String[] args) {
        Main tree = new 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.DFS(0, tree.root)); // 0번 레벨의 100번지 호출
    }
}

 

 

BFS

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

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();
                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 tree = new 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));
    }
}