케빈 베이컨의 6단계 법칙

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


struct Bacon{
    int index, value;
    Bacon(int idx, int val) : index(idx), value(val) {}
};

bool cmp(const Bacon A, const Bacon B) {
    if(A.value == B.value)return A.index < B.index;
    else return A.value < B.value;
}

int N;

int find(const int& start, int& end ,const vector<vector<int>>& v ) {
    vector<int> vis(N, 0);
    vis[start]=1;
    queue<pair<int,int>> q;
    q.push({start, 0});

    int count =1;

    while(!q.empty()) {
        int cur = q.front().first;
        int dist = q.front().second;

        q.pop();

        if(cur ==end) {
            return dist;
        }

        for(int i=0; i< v[cur].size(); i++) {
            int next =v[cur][i];
            if(vis[next]==0) {
                vis[next] =1;
                q.push({next, dist+1});
            }
        }
    }

    return -1;

}


int main() {
    int n; int m;
    cin>> n >> m;
    N =n+1;
    vector<vector<int>> v(n+1);

    for(int i=0; i< m; i++) {
        int x, y;
        cin >> x >>y;
        v[x].push_back(y);
        v[y].push_back(x);
    }

    vector<Bacon> b;

    for(int i=1; i<=n; i++) {
        int sum =0;
        for(int k=1; k<=n; k++) {
            if(i==k)continue;
            int temp = find(i,k,v);
            sum +=temp;
        }
        Bacon bacon(i, sum);
        b.push_back(bacon);
    }

    sort(b.begin(), b.end(), cmp);

    cout << b[0].index;

    return 0;
}

정렬 + 인접리스트

REVIEW

#99클럽 #코딩테스트준비 #개발자취업 #항해99 #TIL