[BOJ/24445번알고리즘수업-너비우선탐색2] c++ / BFS

문제

R 정점부터 시작해서 탐색하였을 때, 1부터 N의 방문된 순서를 출력하는 문제

-인접 정점은 내림차순으로 정렬됨

 

생각

벡터에 정점 간선 정보 넣고, 몇번째 순서가 오는지 확인

벡터 정렬을 어떻게 시켜야할지 몰랐음

sort(시작 주소, 끝주소, 조건)

 

문제풀이

1.양방향 간선이므로, u, v를 서로 푸쉬해줌

2.1부터 N까지 arr[i]의 정점들을 내림차순 해줌

3.정점 R부터 BFS 탐색

4.처음 R 정점은 방문순서 vis = 1 ( cnt = 1 )

5.큐가 빌 때까지 pop

5-1.큐에서 나온 원소의 방문순서는 vis = cnt+1

5-2.큐와 인접한 방문하지 않은 정점 큐에 푸쉬

6.1부터 N 정점의 vis 출력

 

코드

#include <iostream>
#include <algorithm>
#include <queue>
#include <cstring>
#include <vector>
using namespace std;
int N, M, R, u, v, cnt=0;
vector<int> arr[100001];
int vis[100001];
void BFS() {
    queue<int> Q;
    vis[R] = cnt++;
    Q.push(R);

    while (!Q.empty()) {
        int cur = Q.front(); Q.pop();
        vis[cur] = cnt++;

        for ( int i = 0; i < arr[cur].size(); i++ ) {
            if ( vis[arr[cur][i]] ) continue;
            vis[arr[cur][i]] = 1;
            Q.push(arr[cur][i]);
        }
    }
}
int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);

    cin >> N >> M >> R;
    for ( int i = 1; i <= M; i++ ) {
        cin >> u >> v;
        arr[u].push_back(v);
        arr[v].push_back(u);
    }
    for ( int i = 1; i <= N; i++ )
        sort(arr[i].begin(), arr[i].end(), greater<>());

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