[인프런] 07_09 ~ 10 Tree 말단노드까지의 가장 짧은 경로 (DFS, BFS)

📖  문제

---

• 이진트리에서 루트 노드 1에서 말단 노드까지의 길이 중 가장 짧은 길이를 구하는 프로그램을 작성하시오.

트리 예시

출력 예시

⚠️  주의사항

---

• DFS, BFS 두 방법으로 다 풀어보고 어느 방법이 더 좋은지 생각해보기

 

✍️  이해

---

• DFS

/**
 * 1. tree 동일하게 그려주기
 * 2. 최소거리 이므로 root의 lt,rt = null 일 때 return L
 * 3. 그 외의 경우는 Main.min 사용해서 DFS((L+1), root.lt), DFS((L+1), root.rt) 비교 후 값 return
 */

• BFS

/**
 * 1. tree 그려주기
 * 2. Queue 생성 <BFS>
 * 3. root 값 queue 저장
 * 4. queue 값이 빌때까지 반복
 *  4-1. queue.size 만큼 반복
 *   4-1-1. lt,rt == null return line;
 *   4-1-2. lt != null queue.offer(lt)
 *   4-1-3. rt != null queue.offer(rt)
 * 5. return 0 -> 여기까지 올 일 절대로 없음
 */

✏️  풀이

---

• DFS

class DFS_shortest {
    int data;
    DFS_shortest lt, rt;

    public DFS_shortest(int val) {
        data = val;
        lt = rt = null;
    }
}

public class Java07_09 {

    DFS_shortest root;

    public int DFS(int L, DFS_shortest 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) {
        Java07_09 tree = new Java07_09();
        tree.root = new DFS_shortest(1);
        tree.root.lt = new DFS_shortest(2);
        tree.root.rt = new DFS_shortest(3);
        tree.root.lt.lt = new DFS_shortest(4);
        tree.root.lt.rt= new DFS_shortest(5);
        System.out.println(tree.DFS(0 , tree.root));
    }
}

• BFS

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

class BFS_shortest {
    int data;
    BFS_shortest lt, rt;

    public BFS_shortest(int val) {
        data = val;
        lt = rt = null;
    }
}
public class Java07_10 {

    BFS_shortest root;

    public int BFS(BFS_shortest root) {
        Queue<BFS_shortest> queue = new LinkedList<>();
        queue.offer(root);
        int line = 0;
        while (!queue.isEmpty()) {
            int len = queue.size();
            for (int i = 0; i < len; i++) {
                BFS_shortest cur = queue.poll();
                if (cur.lt == null && cur.rt == null) return line;

                if (cur.lt !=null) queue.offer(cur.lt);
                if (cur.rt !=null) queue.offer(cur.rt);
            }
            line ++;
        }
        return 0;
    }

    public static void main(String[] args) {
        Java07_10 tree = new Java07_10();
        tree.root = new BFS_shortest(1);
        tree.root.lt = new BFS_shortest(2);
        tree.root.rt = new BFS_shortest(3);
        tree.root.lt.lt = new BFS_shortest(4);
        tree.root.lt.rt = new BFS_shortest(5);
        System.out.println(tree.BFS(tree.root));
    }
}

---

📋 정리

코드 길이 및 가독성을 봤을 때 DFS가 더 좋아 보이지만 실제로 Stack/Queue/Tree 직접 그려보면서 해봤을 때
BFS가 더 합리적이었습니다.