자바 알고리즘 문제 풀이 입문. ch07. Recursive, Tree, Graph(DFS, BFS 기초) : 이진트리 순회 (BFS : Breadth-First Search)

 

https://hyejin.tistory.com/1258

자바 알고리즘 문제 풀이 입문. ch07. Recursive, Tree, Graph(DFS, BFS 기초) : 부분집합 구하기 (DFS)

-> 이전 문제 풀이 

 

 

7. 이진트리 순회 (BFS : Breadth-First Search) 

설명

아래 그림과 같은 이진트리를 레벨탐색 연습하세요.

 

 

 

예시 출력 1

0 : 1 
1 : 2 3 
2 : 4 5 6 7

 

 

문제 풀이 1

public class BinaryTreeTraversal_width
{
   Node3 root;
   
   public void BFS(Node3 root)
   {
      Queue<Node3> Q = new LinkedList<>();
      Q.offer(root);
      int L = 0;
      while(!Q.isEmpty())
      {
         int len = Q.size(); // Queue의 원소 개수
         System.out.print(L + " : " );
         for (int i = 0; i < len; i++)
         {
            Node3 cur = Q.poll();
            System.out.print(cur.data + " ");
            if (cur.lt != null) Q.offer(cur.lt);
            if (cur.rt != null) Q.offer(cur.rt);
         }
         L++;
         System.out.println();
      }
   }
   public static void main(String[] args)
   {
      BinaryTreeTraversal_width tree = new BinaryTreeTraversal_width();
      tree.root = new Node3(1);
      tree.root.lt = new Node3(2);
      tree.root.rt = new Node3(3);
      tree.root.lt.lt = new Node3(4);
      tree.root.lt.rt = new Node3(5);
      tree.root.rt.lt = new Node3(6);
      tree.root.rt.rt = new Node3(7);
      tree.BFS(tree.root);
   }
}

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

👾 : BFS와 DFS 에 대한 공부를 더 하던가 해야할 것 같다.... 뭐 푸는 방법을 모르니 계속 강의를 듣게 된다 ㅜㅜ 

일단 이번 문제는 

https://hyejin.tistory.com/1257

자바 알고리즘 문제 풀이 입문. ch07. Recursive, Tree, Graph(DFS, BFS 기초) : 이진 트리 순회

이진트리 순회 DFS로 풀었던 것처럼 Node 클래스를 하나 만들고 

 

public void BFS(Node3 root)
{
   Queue<Node3> Q = new LinkedList<>();
   Q.offer(root);
   int L = 0;
   while(!Q.isEmpty())
   {
      int len = Q.size(); // Queue의 원소 개수
      System.out.print(L + " : " );
      for (int i = 0; i < len; i++)
      {
         Node3 cur = Q.poll();
         System.out.print(cur.data + " ");
         if (cur.lt != null) Q.offer(cur.lt);
         if (cur.rt != null) Q.offer(cur.rt);
      }
      L++;
      System.out.println();
   }
}

BFS 메서드를 만들어서 풀었다. BFS는 너비 우선 탐색으로 깊이 우선과 다르게 같은 레벨의 노드를 먼저 출력하고, 그 다음 레벨로 넘어간다. 

이번에는 Queue를 활용해서 문제를 풀어야 하기 때문에 Queue를 하나 선언해준다. 

그 다음 Q에 매개변수로 들어온 root를 먼저 넣어주고, 그 다음 L 변수에 레벨을 0으로 설정해준다. 

 

그리고 Q가 비어있지 않을 때 까지 while문을 돌면서 반복하는데 

len 변수에는 Q의 size를 넣어준다. 그 다음 for문을 len 만큼 돌면서 Queue에 들어있는 원소를 꺼내서 현재 데이터를 출력해주고, 그 다음 현재 node인 cur의 lt rt 가 null 이 아니면 각각 Queue에 넣어주고 이걸 계속 반복해주면 된다. 

 

천천히 생각해보면 

우선 맨 처음에 Node(1) 을 Queue에 넣어주고, L은 0이다. 

Queue에 비어있지 않기 때문에 while 반복문을 도는데 이때 Queue의 size는 1이다. 

그러므로 for문은 0부터 1까지 즉, 한번 돌고 이때 Queue에 있던 Node(1)을 꺼내서 그 노드에 data를 출력한다. -> 1 출력 

그 다음 이 Node(1)의 lt와 rt 가 각각 null 이 아니라면 Queue에 lt, rt Node를 offer 해준다. 

그러면 레벨 0에 있던 Node는 모두 출력한 것이기 때문에 이제 L++를 해서 레벨1로 넘어간다. 

 

레벨 1에는 현재 Queue에 Node(2)와 Node(3)이 들어있다. 

따라서 Queue가 비어있지 않기 때문에 while문을 돌고, 이때 Queue의 size는 2이다.

그러므로 for문은 0부터 2전까지 즉, 2번 돌고 먼저 Queue에 들어있던 Node(2)를 꺼내서 이 노드의 data 값을 출력한다. -> 2 출력

그리고 Node(2)의 lt, rt Node 가 null 이 아니었기 때문에 lt, rt Node를 Queue에 offer 해준다. 

이제 다음 Node(3)을 꺼내서 이 노드의 data 값을 출력한다. -> 3 출력 

그리고 마찬가지로 Node(3)의 lt, rt Node가 null 이 아니기 때문에 lt, rt Node를 Queue에 offer 해준다. 

그러면 레벨 1에 있던 Node는 모두 출력한 것이기 때문에 L++ 해서 레벨2로 넘어간다. 

 

레벨 2에는 현재 Queue에 Node(4), Node(5), Node(6), Node(7)이 들어있다. 

따라서 Queue가 비어있지 않기 때문에 while문을 돌고, 이때 Queue의 size는 4이다. 

그러므로 for문은 4번 돌고, 먼저 Queue에 들어있던 Node(4) 를 꺼내서 이 노드의 data 값을 출력한다. -> 4 출력 

그리고 Node(4)의 lt, rt Node는 null 이기 때문에 Queue에 더 이상 offer 하지 않고 끝난다. 

다음 Node(5)로 넘어와서 data 출력하고 -> 5 출력 Node(4)와 마찬가지로 lt, rt Node 모두 null 이기 때문에 Queue에 offer 하지 않고 다음 Node(6)으로 넘어간다.. 

이렇게 Node(6), Node(7)도 각각 출력 후 -> 6 7 출력 lt, rt Node는 null 이기 때문에 Queue에 offer 하지 않고 종료하며 Queue에 더 이상 Node가 없기 때문에 while문을 종료하고 마무리된다.