[문제풀이] 07-09. 말단 노드까지의 가장 짧은 경로(DFS, BFS)

인프런, 자바(Java) 알고리즘 문제풀이

Recursive, Tree, Graph - 0709. 말단 노드까지의 가장 짧은 경로(DFS, BFS)

---

🗒️ 문제

---

🎈 나의 풀이(DFS)

	private static class Node {
        int data;
        Node lt;
        Node rt;

        public Node(int data) {
            this.data = data;
            lt = rt = null;
        }
    }

    private static int DFS(int level, Node node) {
        if(node.lt == null && node.rt == null) return level;
        return Math.min(DFS(level + 1, node.lt), DFS(level + 1, node.rt));
    }


    public static void main(String[] args) {
        Node 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));
    }

---

🎈 나의 풀이(BFS)

	private static class Node {
        int data;
        Node lt;
        Node rt;

        public Node(int data) {
            this.data = data;
            lt = rt = null;
        }
    }

    private static int BFS(Node node){
        int answer = 0;
        Queue<Node> Q = new LinkedList<>();
        Q.add(node);

        while(!Q.isEmpty()) {
            int len = Q.size();
            for(int i=0; i<len; i++) {
                Node n = Q.poll();
                if(n.lt == null && n.rt == null) return answer;
                Q.add(n.lt);
                Q.add(n.rt);
            }
            answer++;
        }
        return answer;
    }
    public static void main(String[] args) {
        Node 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));
    }

---

🖍️ 강의 풀이(DFS)

  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){ 
          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 tree=new 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)); 
      } 
  } 

---

🖍️ 강의 풀이(BFS)

  class Node{ 
      int data; 
      Node lt, rt; 
      public Node(int val) { 
          data=val; 
          lt=rt=null; 
      } 
  } 

  public class Main{ 
      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[]) { 
          Main tree=new 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.BFS(tree.root)); 
      } 
  } 

---

💬 짚어가기

해당 문제는 DFS와 BFS를 이용해 2가지 방식으로 풀 수 있다.
우선 DFS의 경우 재귀 호출을 수행하다 자식 노드가 없는 시점의 Level을 반환한다.

BFS의 경우도 Queue를 순회하며 자식 노드가 더 이상 존재하지 않는 Level레벨을
반환하여 문제를 해결할 수 있다.