케빈 베이컨의 6단계 법칙 (feat. 백준, 1389번)

케빈 베이컨의 6단계 법칙
https://www.acmicpc.net/problem/1389

1389번: 케빈 베이컨의 6단계 법칙

 

// woohyeon.kim
// kim519620.tistory.com
#include <iostream>
#include <set>
#include <queue>
#include <algorithm>
using namespace std;
set<int> arr[101];
set<pair<int, int>> ans;
int bfs(register int i, register int j){
    bool visit[101]{false};
    queue<pair<int, int>> q;
    q.push(make_pair(i, 0));
    visit[i] = true;
    while(!q.empty()){
        auto p = q.front(); q.pop();
        auto n = p.first, c = p.second;
        for(auto iter = arr[n].begin(); iter != arr[n].end(); ++iter)
            if(!visit[*iter]){
                visit[*iter] = true;
                if(*iter == j)
                    return c + 1;
                q.push(make_pair(*iter, c + 1));
            }
    }
    return 0;
}
int main(){
    ios::sync_with_stdio(false), cin.tie(NULL);
    register int N, M;
    cin >> N >> M;
    for(register int m = 1, a, b; m <= M; ++m)
        cin >> a >> b, arr[a].insert(b), arr[b].insert(a);
    for(register int i = 1, j, v; i <= N; ++i){
        v = 0;
        for(j = 1; j <= N; ++j)
            v += bfs(i, j);
        ans.insert(make_pair(v, i));
    }
    cout << ans.begin()->second;
    return 0;
}
// *&)*@*

 

반응형

1. A-B를 모두 연결시켜줍니다. 만약 1-2, 2-3, 3-4 로 연결되어 있고 1에서 4에 도착하는 최단거리는 3회가 됩니다. (1->2->3->4 이기 때문입니다.)
2. 따라서 bfs를 이용하여 다음 depth로 +1씩 증가시키면서 4가 나올때까지의 최단거리를 찾아주면 됩니다.