Java 최단거리 구하기 알고리즘(DFS, BFS)

아래 그림과 같은 말단 노드까지의 최단 거리 구하기 문제를 DFS와 BFS 방식으로 푼 코드

 

public class Main {
    Node root;
    // 깊이우선탐색
    int DFS(int L, Node node) {
    	// 재귀함수 사용시 종료구문 필수
        if (node.lt == null && node.rt == null) return L;
        // 재귀함수 호출
        else return Math.min(DFS(L+1, node.lt), DFS(L+1, node.rt));
    }
    
    // 넓이우선탐색 (큐 이용)
    int BFS(Node node) {
    	// 동일한 레벨을 의미함
        int L = 0;
        Queue<Node> Q = new LinkedList<>();
        Q.offer(node);

        while (!Q.isEmpty()) {
        	// 시작할때 큐의 사이즈만큼만 돌도록 함( 23,24 라인의 Q.offer()에 의해 Q.size()는 계속 추가됨 )
            int len = Q.size();

            for (int i=0; i<len; i++) {
                Node curr = Q.poll();

                if (curr.lt == null && curr.rt == null) return L;
                if (curr.lt != null) Q.offer(curr.lt);
                if (curr.rt != null) Q.offer(curr.rt);
            }
            L++;
        }
        return L;
    }
    
    public static void main(String[] args) {
    	// 노드에 값 세팅
        Main tree = new Main2();
        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));
        System.out.println(tree.BFS(0, tree.root));
    }
    
    class Node {
        int data;
        Node lt, rt;

        //생성자
        public Node (int data) {
            this.data = data;
            lt = rt = null;
        }
}