[JAVA] 자바 최단경로 알고리즘(Shortest Path) Tree 말단 노드까지의 가장 짧은 경로

Tree 말단 노드까지의 가장 짧은 경로는 "root 노드와 가장 가까운 노드의 길이"를 말한다.

 

 

 

 

 

DFS 깊이 우선 탐색 ver

 

최단경로는 BFS로 푸는게 맞지만 공부하는 단계니까 먼저 DFS로 구현해보았다.

DFS에서는 노드가 자식을 가진다면 무조건 왼쪽, 오른쪽 2개의 자식 노드를 갖는다는 전제가 깔려 있어야 한다.

 

 

import java.util.*;
class Node {
    int data;
    Node lt, rt;
    public Node(int val) {
        data=val;
        lt=rt=null;
    }
}
public class ShortestPath_DFS {
    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) {
        ShortestPath_DFS tree = new ShortestPath_DFS();
        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));
    }
}

매개변수로 L을 추가로 받아 자식이 없다면 L을 리턴하고

자식이 있다면 왼쪽 자식과 오른쪽 자식 중 짧은 L값을 갖는 노드를 반복적으로 찾는다.

 

 

 

 

 

BFS 깊이 우선 탐색 ver

 

import java.util.*;
class Node {
    int data;
    Node lt, rt;
    public Node(int val) {
        data=val;
        lt=rt=null;
    }
}
public class ShortestPath_BFS {
    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) {
        ShortestPath_BFS tree = new ShortestPath_BFS();
        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));
    }
}

Q에 있는 원소 개수만큼 반복하면서 원소 하나를 꺼내 자식이 없다면 L을 리턴하고

왼쪽 혹은 오른쪽 자식이 있을 경우 Q에 넣어주고, 해당 레벨 반복이 끝나면 L값을 증가시켜준다.

 

위의 BFS 버전 풀이는 그래프 상에서 두 노드를 잇는 가장 짧은 경로를 찾는 문제인 최단 경로 알고리즘에 사용되기 때문에 잘 알아두자 !!

 

 

 

 

결과

루트 노드인 1과 오른쪽 자식 노드인 3이 말단노드까지의 가장 짧은 거리가 되고, 정답은 1이 출력된다.

 

 

 

 

출처 : 인프런 자바 알고리즘 문제풀이 입문 : 코딩테스트 대비