[백준/c++] BOJ 24446 - 알고리즘 수업 - 너비 우선 탐색 3

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

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

 

문제 설명

N개의 정점과 M개의 간선으로 구성된 무방향 그래프가 주어진다. 정점 번호는 1번부터 N번이고 모든 간선의 가중치는 1이다. 정점 R에서 시작하여 너비 우선 탐색으로 만들어지는 트리를 너비 우선 탐색 트리라고 한다. 너비 우선 탐색 트리에 있는 모든 노드의 깊이를 출력한다. 방문되지 않는 노드의 깊이는 -1로 출력한다.

N (5 <= N <= 100,000)

M (1 <= M <= 200,000)

R (1 <= R <= N)

해결

간선의 가중치는 모두 1이므로 가중치를 고려하지 않아도 된다.

따라서 벡터에 이어진 정점들을 저장한다.

이후 시작점부터 bfs를 돌며 각 정점들에 도달할 때까지의 거리를 저장해 주면 된다.

코드

#include<bits/stdc++.h>
#define x first
#define y second
using namespace std;

int n, m, r;
vector<int> v[100005];
int visited[100005];

void bfs() {
    queue<int> q;
    q.push(r);
    visited[r] = 1;
    
    while (!q.empty()) {
        auto cur = q.front(); q.pop();
        for (int i = 0; i < v[cur].size(); i++) {
            int nx = v[cur][i];
            if (visited[nx] || nx == r) continue;
            q.push(nx);
            visited[nx] = visited[cur] + 1;
        }
    }
}

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
 
    cin >> n >> m >> r;
    for (int i = 0; i < m; i++) {
        int a, b;
        cin >> a >> b;
        v[a].push_back(b);
        v[b].push_back(a);
    }

    bfs();

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