02. BFS(Breadth-First Search)

1. 특징 및 활용

• 너비 우선 탐색: 시작 정점에서 가까운 정점부터 차례로 탐색하는 방식.
• 최단 경로 탐색: 가중치가 없는 그래프에서 최단 경로임을 보장하는 데 유용하다.
• 실전 사례: 'OfficeWorkerRunning' 포트폴리오에서 특정 구역의 폐쇄 여부를 판단할 때 활용.

2. 복잡도 및 장단점

항목	내용
시간 복잡도	인접 리스트: O(V+E) / 인접 행렬: O(V^2)
공간 복잡도	O(V) (큐에 노드 보관)
장점	가중치 없는 그래프에서 최단 경로 보장
단점	DFS 대비 상대적으로 많은 메모리 사용

3. 구현 코드 (C++)

큐(Queue)를 활용하여 구현하며, 큐에 넣는 시점에 방문 처리를 수행한다.

queue<int> q;
q.push(start);
visited[start] = true;

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

    for (int nxt : adj[cur]) {
        if (visited[nxt]) continue;
        q.push(nxt);
        visited[nxt] = true; // 방문 처리
    }
}

4. 번외: 방문 처리 시점

인접 노드를 탐색하여 큐에 넣는 즉시 방문 처리를 해주어야 중복된 노드가 큐에 쌓이는 것을 방지할 수 있다. 이는 공간 복잡도 관리 측면에서 매우 중요하다.