99클럽 코테 스터디 5일차 TIL + BFS(C++)

문제

[백준] 24444번: 알고리즘 수업 - 너비 우선 탐색 1

https://www.acmicpc.net/problem/24444

 

코드

#include <iostream>
#include <vector>
#include <queue>
#include <algorithm>
using namespace std;

vector<int> visited(100001);
vector<int> graph[100001];
int idx = 1;

void bfs(int R) {
    queue<int> q;
    q.push(R);
    visited[R] = idx++;

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

        for (auto y : graph[x]) {
            if (!visited[y]) {
                q.push(y);
                visited[y] = idx++;
            }
        }
    }
}

int main() {
    int N, M, R;
    cin >> N >> M >> R;

    while (M--) {
        int u, v;
        cin >> u >> v;

        graph[u].push_back(v);
        graph[v].push_back(u);
    }

    for (int i = 1; i <= N; i++)
        sort(graph[i].begin(), graph[i].end());

    bfs(R);

    for (int i = 1; i <= N; i++)
        cout << visited[i] << '\n';

    return 0;
}

 

접근 방법

저번 DFS 문제 풀이와 같지만 탐색 방법이 너비 우선 탐색(BFS)라는 점만 다르다.

BFS는 탐색 시작 시에 큐를 하나 만들고, 시작 노드를 삽입해서 방문 처리한 다음, 아래 과정을 반복하는 알고리즘이다.

• 큐의 맨 앞에 있는 노드를 꺼내서 해당 노드를 방문하고
• 꺼낸 노드에 인접한 노드 중 아직 방문하지 않은 노드를 모두 큐에 추가하고 방문 처리

큐가 빌 때까지 이 과정을 반복하면, 시작 노드에서 가까운 순서대로 모든 노드를 방문하게 된다.

 

단계별 큐의 상태

주어진 예제에서 그래프의 정점은 위와 같이 연결되어 있다.

이때 정점 1부터 BFS를 호출하면 단계별 큐의 상태는 다음과 같이 변화한다.

 

1. 초기 상태
   • q: [1] (시작 정점 1을 큐에 넣음)
   • visited: [0, 1, 0, 0, 0, ...] (정점 1 방문 표시)
2. 1을 꺼내고 인접한 노드들(2, 4)을 큐에 추가
   • q: [2, 4]
   • visited: [0, 1, 2, 0, 3, ...] (2, 4 방문 표시)
3. 2를 꺼내고 인접한 노드들(1, 3, 4)을 확인
   • 1과 4는 이미 방문했으므로 3만 추가
   • q: [4, 3]
   • visited: [0, 1, 2, 4, 3, ...] (3 방문 표시)
4. 4를 꺼내고 인접한 노드들(1, 2, 3)을 확인
   • 모두 이미 방문했으므로 아무것도 추가하지 않음
   • q: [3]
5. 3을 꺼내고 인접한 노드들(2, 4)을 확인
   • 모두 이미 방문했으므로 아무것도 추가하지 않음
   • q: [] (큐가 비었으므로 BFS 종료)