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

01 May 2023 in Algorithm on Java, Coding, Test

문제

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

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

해결방법

• 최단거리를 리턴해야 하므로, 재귀 돌면서 가장 작은 값을 어떻게 뽑을 것인가? 생각해야 함.
• 재귀 돌리며 리턴 값이 어디로 가는지, 가고 나서 어떻게 다음을 실행 하는지 파악.

코드

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 DFS(int L, Node root) {
        // 레벨과 루트 노드를 이용한다.
        // 양쪽 자식 노드 중 1개라도 비어있으면 레벨을 리턴한다. (말단 노드)
        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.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.DFS(0, tree.root));
    }
}