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

✅ BFS란?

BFS (Breadth-First Search, 너비 우선 탐색)는
시작 정점에서 가까운 노드부터 차례대로 탐색하는 알고리즘

• DFS는 "한쪽 길을 끝까지 파고들기"
• BFS는 "지금 위치에서 가까운 곳부터 넓게 퍼져나가기"

---

✅ BFS 특징

 

사용 자료구조	queue (FIFO)
탐색 순서	가까운 곳부터 차례대로
주로 사용하는 상황	최단 거리 구할 때, 레벨 단위 탐색할 때

 

---

✅ BFS 기본 흐름 (2D 맵 기준)

1. 시작 위치를 큐에 push
2. 방문처리
3. 큐에서 하나 꺼내기
4. **상하좌우(혹은 8방향)**을 확인하며 조건에 맞는 이웃을 push
5. 큐가 빌 때까지 반복

---

✅ BFS 예제 (2차원 배열 색칠 문제 기준)

void bfs(vector<vector<char>>& grid, int x, int y, int N, char color) {
    int dx[] = {0, 0, -1, 1};   // x축 이동: 상하좌우
    int dy[] = {-1, 1, 0, 0};   // y축 이동: 상하좌우

    queue<pair<int, int>> q;   // BFS에 사용할 큐
    q.push({x, y});            // 시작점 추가
    grid[y][x] = 0;            // 시작점 방문처리

    while (!q.empty()) {
        auto [cx, cy] = q.front();  // 큐에서 현재 좌표 꺼냄
        q.pop();

        for (int i = 0; i < 4; ++i) {               // 4방향 탐색
            int nx = cx + dx[i];                    // 다음 x
            int ny = cy + dy[i];                    // 다음 y

            // 범위 내 && 같은 색이면
            if (nx >= 0 && nx < N && ny >= 0 && ny < N && grid[ny][nx] == color) {
                grid[ny][nx] = 0;                   // 방문처리
                q.push({nx, ny});                   // 큐에 추가
            }
        }
    }
}

 

✅ 단계별 설명

1. dx[], dy[] 정의

int dx[] = {0, 0, -1, 1};
int dy[] = {-1, 1, 0, 0};

• dx, dy는 이동 방향 (각각 상, 하, 좌, 우 순서를 나타냄)
• 예를 들어 위로 가려면:
  x + dx[0] = x + 0, y + dy[0] = y - 1 → (x, y-1) 즉 위쪽

---

2. 시작 좌표 x, y를 큐에 넣고 방문처리

queue<pair<int, int>> q;
q.push({x, y});
grid[y][x] = 0;

• 시작 위치는 방문 처리 (0으로 변경)
• 큐에 넣어서 BFS 탐색 시작

---

3. 큐가 빌 때까지 반복

while (!q.empty()) {
    auto [cx, cy] = q.front();  // 현재 좌표
    q.pop();

• cx, cy는 현재 탐색 중인 좌표
• front()로 꺼내고 pop()으로 큐에서 제거

---

4. 4방향으로 이웃 확인

    for (int i = 0; i < 4; ++i) {
        int nx = cx + dx[i];
        int ny = cy + dy[i];

• 현재 위치에서 상하좌우 방향으로 한 칸씩 이동하며 이웃 확인

---

5. 방문 조건 확인

        if (nx >= 0 && nx < N && ny >= 0 && ny < N && grid[ny][nx] == color) {

• 좌표가 범위 안에 있는지 확인
• 색깔이 처음과 같은지 확인

---

6. 방문 처리 + 큐에 추가

            grid[ny][nx] = 0;
            q.push({nx, ny});

• 방문했으니 0으로 마킹
• 다음 탐색을 위해 큐에 추가

---

✅ 시각적으로 보면

시작점 (2, 2)
→ 큐에 (2,2) 넣음
→ (2,2)의 상하좌우 체크
→ 같은 색인 (2,3), (1,2) 발견
→ 큐에 넣고 계속 반복
→ 이렇게 인접한 같은 색 모두 탐색 완료!

---

✅ BFS로 연결된 영역 찾기 핵심 포인트

큐 사용	현재 위치 기준, 이웃 순서대로 처리
방문처리	반드시 해야 무한루프 방지됨
좌표 범위 확인	0 <= x < N 꼭 확인해야 함
같은 값 비교	grid[ny][nx] == color 로 탐색

 

---

✅ BFS vs DFS 차이 정리

구조	Stack (재귀 or 수동 stack)	Queue (queue)
탐색 순서	깊게 파고들기	가까운 곳부터 넓게 탐색
용도	모든 경로 탐색, 영역 세기 등	최단 거리 탐색, 거리/레벨 기반 문제
구현 난이도	간단 (재귀)	비교적 쉬움 (queue만 쓰면 됨)