BST 이진 검색 트리(BFS 너비 우선 탐색, 가까운 노드부터, 큐 사용)

✅ BFS (Breadth-First Search, 너비 우선 탐색)

📌 정의

BFS는 루트(또는 시작 노드)에서 가까운 노드부터 차례대로 방문하는 탐색 방식이에요.

• DFS는 한쪽 끝까지 파고들었다가(backtrack) 올라오는 방식이었다면,
• BFS는 먼저 “수평적으로” 넓게 퍼지면서 탐색해요.

---

🧠 어떻게 동작하냐면?

1. 큐(Queue) 를 사용해요. → 선입선출 구조
2. 루트 노드를 큐에 넣고 시작
3. 큐에서 하나 꺼내서 처리하고, 그 노드의 자식들(또는 연결 노드들) 을 큐에 추가
4. 큐가 빌 때까지 반복

---

📊 예시 (이진 트리 기준)

     1
    / \
   2   3
  / \   \
 4   5   6

BFS 순서: 1 → 2 → 3 → 4 → 5 → 6

                  → 위에서부터, 왼쪽에서 오른쪽으로 한 층씩 내려감

 

from collections import deque

class TreeNode:
    def __init__(self, val):
        self.val = val
        self.left = None
        self.right = None

def bfs(root):
    queue = deque()

    if root:
        queue.append(root)
    
    level = 0
    while len(queue) > 0:
        print("level: ", level)
        for i in range(len(queue)):
            curr = queue.popleft()
            print(curr.val)
            if curr.left:
                queue.append(curr.left)
            if curr.right:
                queue.append(curr.right)
        level += 1

 

1) 레벨 0으로 초기화

2) 현재 노드를 큐에 넣는다.

3) 큐에서 빼면서, 현재 노드값 출력

4) 다시 (왼쪽, 오른쪽)  자식 노드 넣는다. 

5) 레벨 증가

6) 큐에 남아있을때까지 계속

---

✅ BFS는 언제 쓰나?

상황	문제 유형이유
최단 거리 구하기	가장 가까운 노드부터 탐색하므로
레벨 순회(level order)	트리의 층별 노드를 구할 때
그래프 탐색에서 경로 찾기	가중치 없는 경우 최단 거리 보장
Flood fill, 토마토 문제 등 퍼지는 현상 시뮬레이션	BFS는 동시에 여러 방향으로 퍼짐

---

✅ LeetCode 대표 문제

문제 번호	제목
102	Binary Tree Level Order Traversal
279	Perfect Squares
733	Flood Fill
542	01 Matrix
994	Rotting Oranges
1091	Shortest Path in Binary Matrix

---

✅ 핵심 요약

구분	DFS	BFS
구조	재귀 or 스택	큐
순서	깊게 → 백트래킹	넓게 → 한 레벨씩
사용	백트래킹, 계산 누적	최단 거리, 퍼짐, 레벨 탐색