[DFS] 9. Tree 말단노드까지의 가장 짧은 경로

*최단 거리는 사실상 BFS로 푼다!!

하지만 공부하는 입장에서 BFS로 시도를 해본다.

 

<<풀이>>

우선 Node class를 만든 후 트리를 만들어준다!

 

L(Level)이 0인 곳 부터 해서 DFS를 시작한다. 이때 DFS는 Level를 반환하므로 타입은 int이다.

 

만약 lt, rt가 null이면 그 곳이 말단이기 때문에 바로 L를 반환한다. 

 

그렇지 않으면 DFS를 지속하는데 Math 내장 클래스를 활용해서 Math.min(DFS(L + 1, root.lt), DFS(L + 1, root.rt)) 를 해줌으로써 

말단 노드까지의 가장 짧은 경로를 return하게 한다.

 

*DFS 같은 경우 왼쪽에 있는 DFS가 먼저 다 계산 된 후 오른 쪽 DFS가 계산 된다. 이를 생각하며 스택을 그려보면서 공부를 계속하자! 그러다보면 DFS의 이해도가 한 층 더 깊어질 것이다~

 

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


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

    }
}

 

오늘도 배워간다!