섹션 7 Recursive, Tree, Graph - 7. 이진트리 순회(넓이우선탐색 : 레벨탐색)

📌 문제 설명

아래와 같은 이진트리를 레벨 순서대로 탐색하는 프로그램을 작성한다.
(넓이우선탐색, BFS 방식으로)

       1
     /   \
    2     3
   / \   / \
  4   5 6   7

---

📝 입력 & 출력

입력

• 트리를 직접 생성한다. (코드에서 하드코딩)

출력

• 트리의 루트 노드부터 시작하여, 같은 레벨의 노드를 왼쪽에서 오른쪽으로 순서대로 출력한다.

---

🔹 예제 입력 & 출력

예제 출력

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

• 각 줄의 맨 앞 숫자는 레벨(Level) 번호를 의미한다.

---

💡 해결 방법

BFS(넓이우선탐색)는 Queue(큐) 자료구조를 사용해 구현한다.

• 루트 노드를 큐에 넣고 시작
• 큐에서 하나씩 꺼내면서 해당 노드를 방문(출력)하고
• 그 노드의 왼쪽 자식, 오른쪽 자식을 큐에 차례로 추가
• 큐가 빌 때까지 이 과정을 반복한다

레벨 단위로 끊어서 출력하려면,
매 레벨마다 큐의 현재 사이즈만큼만 꺼내서 처리한다.

---

💻 코드 구현 (Java)

전체 코드

package partRecursiveTreeGraph;

import java.util.*;

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

public class Problem7 {
	Node root;

	public 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) {
		Problem7 tree = new Problem7();
		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);
		tree.root.rt.lt = new Node(6);
		tree.root.rt.rt = new Node(7);
		tree.BFS(tree.root);
	}
}

---

📖 코드 설명

1️⃣ 큐(Queue) 초기화

BFS는 큐를 사용해서 탐색 순서를 관리한다.

Queue<Node> Q = new LinkedList<>();
Q.offer(root);

• Queue를 생성하고 루트 노드를 먼저 넣는다.
• 이제 이 큐에서 노드를 하나씩 꺼내면서 탐색할 것이다.

2️⃣ BFS 탐색 시작

큐가 비어있지 않은 동안 반복해서 노드를 꺼낸다.

while (!Q.isEmpty()) {

• Q.isEmpty()가 false인 동안 계속 반복
• 매 반복마다 현재 레벨의 노드들을 모두 처리한다.

3️⃣ 현재 레벨 처리

현재 큐에 있는 노드 수(len)만큼만 꺼내서 같은 레벨의 노드를 처리한다.

int len = Q.size();
System.out.print(L + " : ");
for (int i = 0; i < len; i++) {
	Node cur = Q.poll();
	System.out.print(cur.data + " ");

• 현재 큐에 있는 노드 수만큼 for문을 돈다.
• poll()로 노드를 꺼내면서 데이터 출력.

4️⃣ 자식 노드 추가

꺼낸 노드의 왼쪽, 오른쪽 자식이 존재하면 큐에 추가한다.

if (cur.lt != null) Q.offer(cur.lt);
if (cur.rt != null) Q.offer(cur.rt);

• 왼쪽 자식이 있다면 큐에 추가
• 오른쪽 자식이 있다면 큐에 추가
• 추가된 노드는 다음 레벨에 탐색될 예정이다.

5️⃣ 레벨 증가 및 줄바꿈

한 레벨을 다 탐색했으면 레벨을 증가시키고 줄바꿈을 한다.

L++;
System.out.println();

• L을 1 증가시켜 다음 레벨을 준비한다.
• 줄을 바꿔 다음 레벨 노드를 새로 출력한다.

---

⏳ 시간 복잡도 분석

• 트리의 모든 노드를 한 번씩 방문한다 → O(N)
• 각 노드마다 큐에 삽입/삭제 작업을 1번씩 한다 → O(1)씩
• 최종 시간 복잡도: O(N).

---

출처: 인프런 자바(Java) 알고리즘 문제풀이 입문: 코딩테스트 대비

https://www.inflearn.com/course/자바-알고리즘-문제풀이-코테대비/dashboard

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