Tree 말단 노드까지 가장 짧은 경로 (DFS, BFS)

설명

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

 

 

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

 

 

문제 해결

 

사실 이 문제는 최단 거리를 구하는 문제이므로 DFS 보다는 BFS 가 더 적합하다. 연습을 위해 둘 다 풀어보라는 취지같다.

 

< DFS >

 

DFS를 이용하려면 루트 노드부터 시작해 말단 노드에 도달하면 현재 깊이를 반환하고, 부모 노드로 돌아가서 다시 다른 경로를 탐색하고 깊이를 반환하고....의 과정이다. 이를 통해 가장 짧은 길이를 찾으면 된다.

public static 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)); // 말단 노드가 아닐 경우 각각 뻗어나감
}

• L은 현재 노드까지의 깊이(간선의 개수)
• 노드가 말단 노드일 경우 현재 깊이 L를 반환하면 되고
• 노드가 말단 노드가 아닐 경우 왼쪽 자식과 오른쪽 자식으로 DFS를 재귀적으로 호출하고, 두 경로 중 더 짧은 길이를 반환한다.

 

< BFS >

 

DFS를 이용하는 방법은 루트 노드부터 시작해 각 레벨의 모든 노드를 탐색한다. 말단 노드를 만나면 그 노드의 레벨, 즉 깊이가 현재까지 발견된 가장 짧은 경로가 되는 것이다.

public static int BFS(Node root) {
    Queue<Node> queue = new LinkedList<>();
    queue.offer(root);
    int L = 0;
    while (!queue.isEmpty()){
        int len = queue.size();
        for (int i = 0; i < len; i++) {
            Node currentNode = queue.poll();
            if (currentNode.lt == null && currentNode.rt == null) return L; // 말단 노드일 경우 레벨 리턴
            if (currentNode.lt != null) queue.offer(currentNode.lt); // 자식이 있으면 넣어줌
            if (currentNode.rt != null) queue.offer(currentNode.rt);
        }
        L++;
    }
    return 0;
}

• 큐를 사용하여 노드를 저장하고, 각 레벨을 순차적으로 탐색해간다.
• 말단 노드에 처음 도달하면 그 순간의 레벨을 반환하면 된다. (그게 가장 짧은 거리!!)

비교해서 보면 DFS는 모든 경로를 탐색하지만, BFS는 말단 노드를 먼저 발견하는 순간 탐색을 종료하기 때문에 BFS가 훨씬 효율적이라는 걸 알 수 있다.

 

최종 코드

 

< DFS >

public class P09_Tree말단노드까지의가장짧은경로_DFS {

    // 레벨이 즉 거리
    static Node root;
    public static void main(String[] args) {
        root = new Node(1);
        root.lt = new Node(2);
        root.rt = new Node(3);
        root.lt.lt = new Node(4);
        root.lt.rt = new Node(5);
        System.out.println(DFS(0,root));
    }

    public static 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)); //말단 노드가 아닐 경우 각각 뻗어나감

    }
}

 

< BFS >

import java.util.LinkedList;
import java.util.Queue;

public class P10_Tree말단노드까지의가장짧은경로_BFS {
    static Node root;
    public static void main(String[] args) {
        root = new Node(1);
        root.lt = new Node(2);
        root.rt = new Node(3);
        root.lt.lt = new Node(4);
        root.lt.rt = new Node(5);
        System.out.println(BFS(root));
    }

    public static int BFS(Node root) {
        Queue<Node> queue = new LinkedList<>();
        queue.offer(root);
        int L = 0;
        while (!queue.isEmpty()){
            int len = queue.size();
            for (int i = 0; i < len; i++) {
                Node currentNode = queue.poll();
                if (currentNode.lt == null && currentNode.rt == null) return L; //말단 노드일 경우 레벨 리턴
                if (currentNode.lt != null) queue.offer(currentNode.lt); //자식이 있으면 넣어줌
                if (currentNode.rt != null) queue.offer(currentNode.rt);
            }
            L++;
        }
        return 0;
    }
}