BFS

BFS 개념

한 줄 정의

• BFS(Breadth-First Search)는 시작 정점에서 가까운 정점부터 거리 순서(레벨 순서)로 탐색하는 알고리즘입니다.

동작 원리

1. 시작 정점을 큐에 넣고 발견 처리한다.
2. 큐에서 하나 꺼내 그 정점의 인접 정점을 확인한다.
3. 아직 발견하지 않은 정점이면 큐에 넣고, 부모/거리 정보를 기록한다.
4. 큐가 빌 때까지 반복한다.

BFS vs DFS 핵심 차이

항목	BFS	DFS
탐색 순서	가까운 정점부터	한 경로를 끝까지
핵심 자료구조	큐(queue)	스택(재귀 포함)
비가중치 최단거리	보장	보장 안 함

discovered(예약) 개념

• BFS는 큐에 넣는 순간 discovered = true로 처리해야 중복 삽입을 막을 수 있습니다.
• 즉, “큐에 넣음 = 예약”, “큐에서 꺼냄 = 실제 처리”로 이해하면 실수가 줄어듭니다.

---

BFS 구현 패턴

인접 리스트 + 큐 (권장 기본형)

int V = 6;
vector<vector<int>> adj(V);

vector<bool> discovered(V, false);
vector<int> parent(V, -1);
vector<int> dist(V, -1);

void Bfs(int start) {
    queue<int> q;
    q.push(start);
    discovered[start] = true;
    parent[start] = start;
    dist[start] = 0;

    while (!q.empty()) {
        int here = q.front();
        q.pop();

        cout << "Visited: " << here << '\n';

        for (int there : adj[here]) {
            if (discovered[there]) continue;
            q.push(there);
            discovered[there] = true;
            parent[there] = here;
            dist[there] = dist[here] + 1;
        }
    }
}

인접 행렬 버전

vector<vector<int>> matrix(V, vector<int>(V, 0)); // 0: 미연결, 1: 연결

void BfsMatrix(int start) {
    queue<int> q;
    q.push(start);
    discovered[start] = true;
    parent[start] = start;
    dist[start] = 0;

    while (!q.empty()) {
        int here = q.front();
        q.pop();

        for (int there = 0; there < V; there++) {
            if (matrix[here][there] == 0) continue;
            if (discovered[there]) continue;

            q.push(there);
            discovered[there] = true;
            parent[there] = here;
            dist[there] = dist[here] + 1;
        }
    }
}

끊긴 그래프 전체 탐색

void BfsAll() {
    fill(discovered.begin(), discovered.end(), false);
    fill(parent.begin(), parent.end(), -1);
    fill(dist.begin(), dist.end(), -1);

    for (int v = 0; v < V; v++) {
        if (discovered[v]) continue;
        Bfs(v);
    }
}

• 한 시작점으로는 한 컴포넌트만 탐색됩니다.
• 전체 정점을 보고 싶다면 BfsAll() 패턴이 필요합니다.

---

parent / distance 활용

의미

• parent[v]: v를 처음 발견하게 만든 이전 정점
• dist[v]: 시작점에서 v까지의 최단 간선 수

경로 복원

vector<int> BuildPath(int start, int target) {
    vector<int> path;
    if (dist[target] == -1) return path; // 도달 불가

    int cur = target;
    while (cur != start) {
        path.push_back(cur);
        cur = parent[cur];
    }
    path.push_back(start);
    reverse(path.begin(), path.end());
    return path;
}

• BFS 한 번으로 방문 순회 + 거리 계산 + 경로 복원을 모두 처리할 수 있습니다.

---

BFS와 최단 거리

왜 최단거리인가?

• BFS는 거리 0층 -> 1층 -> 2층 순서로 탐색합니다.
• 어떤 정점 v에 처음 도달한 순간이 start -> v의 최소 간선 수입니다.

성립 조건

• 모든 간선 비용이 동일(보통 1)인 그래프
• 즉, 비가중치 최단거리 문제에서 BFS가 정답입니다.

성립하지 않는 경우

• 간선마다 비용이 다르면 BFS는 최단 비용을 보장하지 않습니다.
• 이때는 다익스트라(음수 없음), 벨만-포드(음수 가능)를 고려해야 합니다.

---

시간/공간 복잡도

표현 방식	시간 복잡도	이유
인접 리스트	O(V + E)	각 정점/간선을 최대 1회 처리
인접 행렬	O(V^2)	각 정점마다 전체 열 스캔

공간 복잡도:

• queue, discovered, parent, dist 등으로 O(V)

---

BFS 한계와 확장

• 목적지 정보 없음: 기본 BFS는 사방으로 균등 확산
• 가중치 미지원: 간선 비용이 다르면 비효율/오답 가능
• 확장 알고리즘:
  • 가중치(음수 없음): 다익스트라
  • 목적지 방향 유도: A*
  • 가중치가 0 또는 1: 0-1 BFS(deque)

---

자주 하는 실수 + 체크 질문

자주 하는 실수

실수	문제
큐에서 꺼낼 때 발견 처리	같은 정점이 큐에 중복 삽입됨
dist 초기값 미설정	도달 불가 정점 판별 실패
parent 갱신 타이밍 오류	경로 복원 오류
BFS인데 스택 사용	탐색 순서가 DFS처럼 바뀜

체크 질문 (스스로 답해보기)

• BFS에서 discovered를 push 시점에 켜는 이유는?
• BFS가 비가중치 최단거리를 보장하는 핵심 논리는?
• 끊긴 그래프에서 전체 탐색을 하려면 어떤 패턴이 필요한가?
• 간선 비용이 서로 다르면 BFS 대신 무엇을 써야 할까?

---