개발 다이어리

코드

package algorithm07;

import java.util.*;

class Node2{ 
    int data; 
    Node2 lt, rt; 
    public Node2(int val) { 
        data=val; 
        lt=rt=null; 
    } 
} 
  
public class BFS레벨탐색{ 
    Node2 root; 
    public void BFS(Node2 root){ 
        Queue<Node2> Q=new LinkedList<>();
        Q.add(root);
        int L=0;
        while(!Q.isEmpty()){
            // for문에서 Q.size()를 조건식으로 주면 메서드 이기 때문에 상태 변화에 따라 값이 변동된다.
            int len = Q.size(); 
            System.out.print(L+" : ");
            for(int i=0; i<len; i++){
                Node2 cur = Q.poll();
                System.out.print(cur.data+" ");
                if(cur.lt!=null) Q.add(cur.lt);
                if(cur.rt!=null) Q.add(cur.rt);
            }
            L++;
            System.out.println();
        }
    } 
    
    public static void main(String args[]) { 
        BFS레벨탐색 tree=new BFS레벨탐색(); 
        tree.root=new Node2(1); 
        tree.root.lt=new Node2(2); 
        tree.root.rt=new Node2(3); 
        tree.root.lt.lt=new Node2(4); 
        tree.root.lt.rt=new Node2(5); 
        tree.root.rt.lt=new Node2(6); 
        tree.root.rt.rt=new Node2(7);
        tree.BFS(tree.root); 
    } 
}

결과

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

L 을 기준으로 큐 자료구조를 사용하여 탐색해 나아간다.

DFS와 달리 큐를 사용해 탐색해 나아가므로 재귀호출을 하지 않는다.(큐 특징, FIFO, 선입선출)

위 예제에서 int size = Q.size(); 따로 변수로 빼서 사용한 이유는 Q.size()가 메서드이기 때문이다.

Q가 poll()한다면 Q의 상태가 변화했으므로 size()메서드도 변동된다. 

따라서 L별 최초 너비 탐색 직전에 size() 상태를 저장해 놓고 같은 L에 속하는 모든 노드를 탐색하게 된다.

왜 큐 자료구조와 size() 메서드를 상태 값을 따로 로컬 변수로 저장해 반복문을 더 사용하는지 알아보자

현재 데이터 구조는 위와 같다.

L 이 0일 때는 문제 없어보인다.

L이 1일때 Q는 [2,3]을 저장하고 있고, 우리가 원하는 것은 이 과정에서 다음 탐색 L 2 노드데이터인 4,5는 다음에 처리하고 싶을 것이다.

그렇기에 L 값이 변하고 최초 너비 탐색 시 size()값을 저장하여 사용하는 것이다.

또한 큐 특성상 선입선출이므로 앞자리부터 사용하기에 큐를 사용하는 것이다.

엄밀히 말하면 선입선출은 배열을 기반으로 한 ArrayList로 사용은 가능하지만 빈 공간 메꾸는 작업으로 엄청난 비효율이 발생하게 된다. 따라서 LinkedList를 사용한 것이다.

L1의 노트 3 까지 다 탐색한다면 비로소 for문 조건식이 false가 되며, 다음 L++ 너비를 탐색하게 된다.