👕 Tree 말단 노드까지의 가장 짧은 경로

👖 문제

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

👖 BFS 풀이

🧦 노드 트리

노드 만들기

class Node2{
    int data;
    Node2 lt,rt;
    public Node2(int val){
        data = val;
        lt = rt = null;
    }
}

메인 메소드

public static void main(String[] args){
        // 트리 만들기
        Main68_DFS tree = new Main68_DFS();
        tree.root = new Node2(1);
        tree.root.lt = new Node2(2);
        tree.root.rt = new Node2(3);
        tree.root.lt.lt = new Node2(4);
        tree.root.lt.rt = new Node2(5);
        System.out.println(tree.DFS(0, tree.root));
    }

🧦 과정을 살펴보자.

public 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));
}

메인 메소드의
System.out.println(tree.DFS(0, tree.root));
실행을 하면 위와 같이 DFS메소드를 실행한다.

DFS(0,100) 의 lt,rt가 null 이 아니기 때문에,else문으로 넘어가 DFS(L+1,root.lt)를 실행한다.

위와 같은 방법으로 DFS(1,200)을 다시 호출하면, D(1,200)의 lt값이 존재하므로 D(2,400)이 호출된다.

D(2,400)의 lt,rt의 값이 존재하지 않으므로 D(2,400)은 2를 return하게 된다.

else return Math.min(DFS(L+1, root.lt), DFS(L+1, root.rt));
코드 중 DFS(L+1,root.lt) 처리가 되었으니 다시 DFS(L+1, root.rt)를 처리해야한다.

DFS(재귀) 👖 소스코드

package algolecture;

class Node2{
    int data;
    Node2 lt,rt;
    public Node2(int val){
        data = val;
        lt = rt = null;
    }
}

public class Main68_DFS {
    Node2 root;
    public int DFS(int L, Node2 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) {
        // 트리 만들기
        Main68_DFS tree = new Main68_DFS();
        tree.root = new Node2(1);
        tree.root.lt = new Node2(2);
        tree.root.rt = new Node2(3);
        tree.root.lt.lt = new Node2(4);
        tree.root.lt.rt = new Node2(5);
        System.out.println(tree.DFS(0, tree.root));
    }
}

BFS 👖 소스코드

package algolecture;
import java.util.LinkedList;
import java.util.Queue;

class Node3 {
    int data;
    Node3 lt,rt;
    public Node3(int val){
        data = val;
        lt= rt= null;
    }
}

public class Main68_BFS {
    Node3 root;
    public int BFS(Node3 root){
        Queue<Node3> Q = new LinkedList<>();
        Q.offer(root);
        int L = 0;
        while(!Q.isEmpty()) {
            int len = Q.size();
            for (int i = 0; i < len; i++) {
                Node3 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) {
        Main68_BFS tree = new Main68_BFS();
        tree.root = new Node3(1);
        tree.root.lt = new Node3(2);
        tree.root.rt = new Node3(3);
        tree.root.lt.lt = new Node3(4);
        tree.root.lt.rt = new Node3(5);
        System.out.println(tree.BFS(tree.root));
    }
}