[알고리즘/java] 이진트리 레벨탐색(BFS)

이 글은 인프런 [자바(Java) 알고리즘 문제풀이 : 코딩테스트 대비 ] 강의를 수강하며 작성한 글입니다.

- https://inf.run/Azjw

자바(Java) 알고리즘 문제풀이 : 코딩테스트 대비 - 인프런 | 강의

 

BFS는 Breadth-First Search, 넓이 우선 탐색이다.

 

위의 트리를 예시로 BFS 탐색을 해본다면,

 

0레벨 : 1

1레벨 : 2 3

2레벨 : 4 5 6 7 

 

이므로 1 2 3 4 6 7 순서대로 탐색이 된다.

 

 

BFS는 보통 '어떤 지점에서 특정 지점까지의 최단 거리'를 구할 때 많이 쓰이며, 큐(Queue)를 이용해 구현한다.

 

<예제코드>

class Node {
	int data;
	Node lt, rt;

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

public class Main {

	private static Node root;

	public static void BFS(Node root) {
		Queue<Node> Q = new LinkedList<>();
		Q.offer(root);

		int L = 0; // 레벨

		while (!Q.isEmpty()) {
			int len = Q.size();
			System.out.print(L + " : ");
			for (int i = 0; i < len; i++) {
				Node 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) {
		// TODO Auto-generated method stub
		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);
		root.rt.lt = new Node(6);
		root.rt.rt = new Node(7);

		BFS(root);

	}

}

>> 노드 클래스를 정의하여 맨 위의 트리구조를 만든다.

 

< BFS 원리 >

 

1.

처음 루트노드인 1을 큐에 넣고 해당 레벨을 의미하는 L은 0이다.

현재 큐에는 루트 노드 1이 있는 상태이며, 큐의사이즈(len)는 1이다.

 

큐 : 1

 

그 다음 Q.poll()을 하여 1을 출력하고, 0의 왼쪽 자식과 오른쪽 자식이 있으므로 각각 큐에 offer()해준다.

 

출력 : 0 : 1

큐 : 2 3

 

len이 1이기때문에 반복문을 종료하고 L++을 하여 다음 레벨 탐색을 한다.

 

2. 

현재 큐에는 2, 3이 있는 상태며 큐의사이즈(len)는 2, L=1이다.

 

큐 : 2 3

 

그 다음 Q.poll()을 하여 2을 출력하고, 2의 왼쪽 자식과 오른쪽 자식이 있으므로 각각 큐에 offer()해준다.

 

출력 : 0 : 1

        1 : 2

큐 : 3 4 5

 

len이 2이기때문에 한 번 더 반복한다.

 

큐 : 3 4 5

 

그 다음 Q.poll()을 하여 3을 출력하고, 3의 왼쪽 자식과 오른쪽 자식이 있으므로 각각 큐에 offer()해준다.

 

출력 : 0 : 1

        1 : 2 3

큐 :  4 5 6 7

 

반복문을 종료하고 L++을 하여 다음 레벨 탐색을 한다.

 

 

3. 

현재 큐에는 4, 5, 6, 7이 있는 상태며 큐의사이즈(len)는 4, L=2이다.

 

큐 : 4 5 6 7

 

그 다음 Q.poll()을 하여 4을 출력하고, 4의 왼쪽 자식과 오른쪽 자식이 없으므로 offer()없이 i++

 

출력 : 0 : 1

        1 : 2 3

        2 : 4

큐 : 5 6 7

 

현재 큐에는 5, 6, 7이 있는 상태다.

 

큐 : 5 6 7

 

그 다음 Q.poll()을 하여 5을 출력하고, 5의 왼쪽 자식과 오른쪽 자식이 없으므로 offer()없이 i++

 

출력 : 0 : 1

        1 : 2 3

        2 : 4 5

큐 : 6 7

 

현재 큐에는 6, 7이 있는 상태다.

 

큐 : 6 7

 

그 다음 Q.poll()을 하여 6을 출력하고, 6의 왼쪽 자식과 오른쪽 자식이 없으므로 offer()없이 i++

 

출력 : 0 : 1

        1 : 2 3

        2 : 4 5 6

큐 : 7

 

현재 큐에는 7이 있는 상태다.

 

큐 : 7

 

그 다음 Q.poll()을 하여 7을 출력하고, 7의 왼쪽 자식과 오른쪽 자식이 없으므로 offer()없이 i++

 

출력 : 0 : 1

        1 : 2 3

        2 : 4 5 6 7

큐 : 

 

len이 4이기 때문에 for문을 종료하고, 큐에 원소가 하나도 없기 때문에 (Q.isEmpthy() 만족)

while문을 종료하여 탐색을 끝낸다.