자바 알고리즘 문제 풀이 입문. ch07. Recursive, Tree, Graph(DFS, BFS 기초) : Tree 말단 노드까지의 가장 짧은 경로 (BFS)

 

https://hyejin.tistory.com/1261

자바 알고리즘 문제 풀이 입문. ch07. Recursive, Tree, Graph(DFS, BFS 기초) : Tree 말단 노드까지의 가장 짧

-> 이전 문제 풀이 

 

 

 

10. Tree 말단 노드까지의 가장 짧은 경로 (BFS) 

설명

아래 그림과 같은 이진트리에서 루트 노드 1에서 말단노드까지의 길이 중

가장 짧은 길이를 구하는 프로그램을 작성하세요.

각 경로의 길이는 루트노드에서 말단노드까지 가는데 이동하는 횟수를 즉 간선(에지)의 개수를 길이로 하겠습니다.

 

 

 

출력 

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

 

 

문제 풀이 1 

public class ShortestLengthToEndNode3
{
   Node root;
   
   public int BFS(Node root)
   {
      int L = 0;
      Queue<Node> Q = new LinkedList<>();
      Q.offer(root);
      
      while (!Q.isEmpty())
      {
         int len = Q.size();
         for (int i = 0; i < len; i++)
         {
            Node cur = Q.poll();
            if (cur.lt != null) {
               Q.offer(cur.lt);
            }else {
               return L;
            }
            
            if (cur.rt != null)
            {
               Q.offer(cur.rt);
            }else {
               return L;
            }
         }
         
         L++;
      }
      
      return L;
   }
   
   public static void main(String[] args)
   {
      ShortestLengthToEndNode3 tree = new ShortestLengthToEndNode3();
      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);
      
      int result = tree.BFS(tree.root);
      System.out.println(result);
   }
}

 

👩‍💻 : 이전 문제와 설명은 동일한데 푸는 방법을 저번 풀이는 DFS 이고, 이번 풀이는 BFS로 푸는 방법이다. 

사실 짧은 거리 구하는 문제에 대해서는 DFS보다는 BFS로 풀어야 한다..!! 

 

public int BFS(Node root)
{
   int L = 0;
   Queue<Node> Q = new LinkedList<>();
   Q.offer(root);
   
   while (!Q.isEmpty())
   {
      int len = Q.size();
      for (int i = 0; i < len; i++)
      {
         Node cur = Q.poll();
         if (cur.lt != null) {
            Q.offer(cur.lt);
         }else {
            return L;
         }
         
         if (cur.rt != null)
         {
            Q.offer(cur.rt);
         }else {
            return L;
         }
      }
      
      L++;
   }
   
   return L;
}

우선 BFS로 풀기 위해 Queue를 선언해주고, 다음 L에 레벨 0을 넣어줬다. 이 L이 간선의 개수, 즉 거리가 될 것이다. 

그리고 Q에 node 1을 먼저 넣어주고, while문을 반복하면서 Q가 비어있지 않을때까지 반복해준다. 

 

Q의 size를 구해서 for문을 도는데 이때 Q에서 꺼내서 현재 cur의 lt와 rt가 비어있지 않으면 Q에 offer 해주고, null이면 말단 노드라는 뜻이기 때문에 L 현재 레벨을 리턴해준다. (그게 가장 짧은 거리의 노드이기 때문) 

 

for문을 다 돌았다는 것은 모두 말단 노드가 아니었다는 것이기 때문에 레벨을 +1 해주고, 다시 이 과정을 반복해주면 된다. 

 

 

문제 풀이 2

public class ShortestLengthToEndNode4
{
   
   Node root;
   
   public int BFS(Node root)
   {
      Queue<Node> Q = new LinkedList<>();
      int L = 0;
      Q.offer(root);
      
      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 L;
      
   }
   
   public static void main(String[] args)
   {
      ShortestLengthToEndNode4 tree = new ShortestLengthToEndNode4();
      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);
      
      int result = tree.BFS(tree.root);
      System.out.println(result);
      
   }
}

 

👾 : 이건 강사님 풀이인데, 훨씬 깔끔하다. ㅎㅎ 

if (cur.lt == null && cur.rt == null) return L;

이 부분이 다른데 말단 노드이려면 lt와 rt 모두 없을 때 최단 거리이기 때문에 사실 내가 푼 풀이는 트리 구조가 좀 달랐으면 틀렸을 것 같다..! 왜냐하면 lt 값은 있고 rt 값은 없을 수도 있는데 이럴 때 내가 푼 풀이는 이 조건에서도 최단거리라고 return L 할 것이기 때문이다. 

 

따라서 lt와 rt 가 모두 null 일 때만이 말단 노드이므로 이럴때만 return L 해주고,

lt와 rt 중 하나라도 null 이면 Q에 offer 해줘야 한다.