[BOJ 24446] 알고리즘 수업 - 너비 우선 탐색 3 C++

난이도: Silver 2
번호: 24446
생성일: March 4, 2023 12:44 PM
알고리즘 분류: 그래프 이론, 그래프 탐색, 너비 우선 탐색
언어: C++

24446번: 알고리즘 수업 - 너비 우선 탐색 3

C++

#include <iostream>
#include <queue>
#include <iostream>
#include <vector>

using namespace std;

int N, M, R;
vector<int> path[100001];

vector<int> BFS(int R)
{
    vector<int> dist(N + 1, -1);
    queue<int> Q;
    Q.push(R);
    dist[R] = 0;

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

        for (auto &next : path[cur])
        {
            if (dist[next] != -1)
                continue;
            dist[next] = dist[cur] + 1;
            Q.push(next);
        }
    }
    return dist;
}

int main(void)
{
    cin.tie(0)->ios::sync_with_stdio(0);
    cout.tie(0);

    cin >> N >> M >> R;

    for (int i = 0; i < M; i++)
    {
        int a, b;
        cin >> a >> b;
        path[a].push_back(b);
        path[b].push_back(a);
    }

    auto dist = BFS(R);

    for (int i = 1; i <= N; i++)
        cout << dist[i] << "\n";
}