[BOJ/1389번케빈베이컨의6단계 법칙] c++ / BFS

문제

유저 중에서 케빈 베이컨의 6단계 법칙에 의해 관계 수가 가장 적은 사람을 출력하는 문제

-케빈 베이컨의 6단계 법칙 : 모든 사람은 최대 6단계 이내에서 서로 아는 사람으로 연결됨

 

생각

일반 BFS 문제에 유저수만 더해주면 되겠다고 생각함

 

문제풀이

1.유저별로 BFS 탐색함

-큐에 푸쉬할 때, {유저, 관계 단계} / {nx, cnt}

2.유저와 연결된 친구 수 만큼 반복문 돌려서 탐색하는데, 방문표시가 없으면 큐에 푸쉬(cnt+1) + 방문표시

3.유저 관계수 배열(re)에 cnt씩 더해줌

4.관계수가 가장 적은 유저 출력

 

코드

// 유저의 친구 수를 담은 배열
#include <iostream>
#include <algorithm>
#include <queue>
#include <vector>
using namespace std;
#define X first
#define Y second
vector<int> user[101];
int f[101], re[101], vis[101];
int N, M, x, y, cnt;
void BFS() {
    queue<pair<int, int>> Q; // 번호와 cnt

    for ( int i = 1; i <= N; i++ ) {
        for ( int k = 1; k <= N; k++ ) // 초기화
            vis[k] = 0;
        
        Q.push({i, 0});
        vis[i] = 1;
        while(!Q.empty()) {
            int nx = Q.front().X;
            int cnt = Q.front().Y;
            Q.pop();

            re[i] += cnt;

            for ( int j = 0; j < user[nx].size(); j++ ) {
                if ( vis[user[nx][j]] ) continue;

                vis[user[nx][j]] = 1;
                Q.push({user[nx][j], cnt+1});
            }
        }
    }
}
int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);

    cin >> N >> M;
    for ( int i = 0; i < M; i++ ) {
        cin >> x >> y;
        user[x].push_back(y);
        user[y].push_back(x);
        f[x]++;
        f[y]++;
    }
    BFS();
    
    int min = re[1];
    int idx = 1;
    for ( int i = 2; i <= N; i++ ) {
        if ( min > re[i] ) {
            idx = i;
            min = re[i];
        }
    }

    cout << idx;
}