백준 1389번: 케빈 베이컨의 6단계 법칙 (C++)

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

정점별로 연걸된 나머지 정점까지의 거리의 합을 구하고, 그 합의 최솟값을 가지는 정점의 번호를 출력해주면 된다.

인접행렬을 만들 때, 방향성이 없는 그래프라는 것을 주의하자.

#pragma warning(disable :4996)
#include<iostream>
#include<queue>
using namespace std;
 
int grp[101][101]; // 1-indexed
int n, m; //유저수, 관계수
int dis[101]; //방문처리 + 거리
queue<int> q;
 
void bfs(int st) {
    q.push(st);
    dis[st]++;
    while (!q.empty()) {
        int qs = q.size();
        while (qs--) {
            int cur = q.front();
            q.pop();
            for (int i = 1; i <= n; i++) {
                if (grp[cur][i] != 1 || dis[i] >= 0) continue;
                q.push(i);
                dis[i] = dis[cur] + 1;
            }
        }
    }
}
 
int main(void) {
    ios::sync_with_stdio(false);
    cin.tie(0);
    
    cin >> n >> m;
    for (int i = 0; i < m; i++) {
        int src, dst;
        cin >> src >> dst;
        grp[src][dst] = 1;
        grp[dst][src] = 1; //무방향성
    }
 
    int Min = 100000000, ans;
    for (int i = 1; i <= n; i++) {
        for (int i = 1; i <= n; i++) //방문처리 배열 초기화
            dis[i] = -1;
        bfs(i);
        int Sum = 0;
        for (int i = 1; i <= n; i++)
            Sum += dis[i];
        if (Sum < Min) {
            Min = Sum;
            ans = i;
        }
    }
    cout << ans;
    
    return 0;
}