BFS

1. BFS 기본 개념

• 큐(Queue) 기반 탐색 (선입선출FIFO)
• 가까운 곳부터 탐색 → 최단 거리 보장
  → 그래서 최단 거리 문제, 레벨 탐색 문제에 BFS가 잘 쓰임

2. 자주 쓰는 패턴

(1) 기본 뼈대

queue<int> q;
vector<bool> visited(N, false);

void bfs(int start) {
    q.push(start);
    visited[start] = true;

    while(!q.empty()) {
        int cur = q.front(); q.pop();
        for(int nxt : adj[cur]) {
            if(!visited[nxt]) {
                visited[nxt] = true;
                q.push(nxt);
            }
        }
    }
}

• visited 체크는 큐에 넣을 때 해야 중복 방지됨
• 그래프는 보통 vector<vector> adj 로 저장

(2) 2D 격자(미로 탐색, 영역 탐색)

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

void bfs(int sx, int sy) {
    queue<pair<int,int>> q;
    visited[sx][sy] = true;
    q.push({sx, sy});

    while(!q.empty()) {
        auto [x, y] = q.front(); q.pop();
        for(int d=0; d<4; d++) {
            int nx = x + dx[d], ny = y + dy[d];
            if(nx<0 || ny<0 || nx>=n || ny>=m) continue; // 범위 체크
            if(!visited[nx][ny] && grid[nx][ny]==1) {
                visited[nx][ny] = true;
                q.push({nx, ny});
            }
        }
    }
}

• dx, dy 배열 미리 선언
• 범위(nx<0, nx>=n) 항상 체크
• 조건(grid[nx][ny] == 1) 문제에 따라 달라짐

(3) 최단 거리 BFS (가중치 없는 그래프)

vector<int> dist(N, -1); // 거리 저장
queue<int> q;

void bfs(int start) {
    q.push(start);
    dist[start] = 0;

    while(!q.empty()) {
        int cur = q.front(); q.pop();
        for(int nxt : adj[cur]) {
            if(dist[nxt] == -1) {
                dist[nxt] = dist[cur] + 1;
                q.push(nxt);
            }
        }
    }
}

• dist 배열 초기화는 -1
• dist[nxt] = dist[cur] + 1 로 갱신
• visited 대신 dist 체크하면 됨

3. BFS 문제 유형별 키워드

• 미로 탐색 → 2D BFS, dx,dy 배열
• 최단 거리 → 거리 배열 dist
• 연결된 영역 세기 → BFS로 영역 하나 탐색 후 카운트
• 다중 시작점 (불 퍼짐, 바이러스 전파) → 큐에 여러 시작점 push 하고 시작
• 가중치 없는 최단 경로 → BFS
• 가중치 1, 0 (예: 벽 부수고 이동) → deque 이용하는 0-1 BFS

---

BFS에서 큐를 사용하는 이유

1. 탐색 순서를 보장해야 함
   • BFS는 현재 위치에서 가까운 노드부터 차례로 방문해야 최단 거리를 보장함.
   • 큐를 사용하면 삽입한 순서대로 탐색 가능 → 가장 먼저 들어온 노드를 먼저 처리(FIFO)
   • 벡터를 쓰면, 매번 가장 앞쪽 원소를 삭제해야 하는데, 이는 O(N) 연산이 발생해 비효율적임.
2. 벡터로 대체하면 성능 저하 발생
   • vector를 사용하면 push_back()으로 삽입은 O(1)이지만,front() 원소를 삭제하려면 O(N) 연산이 필요 (앞 요소 삭제 후 나머지 이동 필요).
   • 반면 queue는 pop()이 O(1)이라 빠르게 요소를 제거할 수 있음.
3. 탐색 경로를 효율적으로 관리할 수 있음
   • queue를 쓰면 방문할 노드를 순서대로 저장하고, 한 번 방문한 노드는 다시 탐색하지 않도록 관리할 수 있음.
   • BFS는 “가까운 곳부터 순차 탐색”을 보장해야 하므로, 큐를 쓰는 것이 자연스러움.

결론: BFS에서는 큐 사용

• FIFO 구조를 유지해야 최단 거리 탐색을 보장 → 큐가 적합
• 벡터는 erase(begin()) 시 O(N) 연산이 필요해 비효율적
• queue는 pop()이 O(1)이라 빠르게 처리 가능