[알고리즘/java] 인프런 자바 알고리즘 강의 : 이진트리 레벨탐색(BFS)

[알고리즘/java] 인프런 자바 알고리즘 강의 : 이진트리 레벨탐색(BFS)

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

- https://inf.run/Azjw

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 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문을 종료하여 탐색을 끝낸다.

from http://bumbleb22.tistory.com/10 by ccl(A) rewrite - 2021-12-14 19:00:54