1389(케빈 베이컨의 6단계 규칙)

문제

케빈 베이컨의 6단계 법칙에 따르면 지구상의 모든 사람은 최대 6단계 내에서 지인으로 연결될 수 있습니다. Kevin Bacon 게임은 임의의 두 사람이 가능한 한 적은 단계로 서로를 안내할 수 있는 게임입니다.

예를 들어, 전혀 무관해 보이는 인하대 이강호와 서강대 민세희를 몇 단계로 연결할 수 있을까?

천민호는 이강호와 같은 학교에 다닌다. 천민호와 최백준이 백준온라인판사를 통해 만났다. 최백준과 김선영이 함께 스타트링크를 창업했다. 김선영과 김도현은 같은 학교 동아리 소속이다. 김도현과 민세희는 같은 학교를 나와 서로를 알고 있다. 즉 이강호-천민호-최백준-김선영-김도현-민세희 5단계만 거치면 된다.

Kevin Bacon은 미국 할리우드 배우들과 Kevin Bacon 게임을 플레이하는 총 단계 수가 가장 적은 사람으로 간주됩니다.

오늘은 백준온라인저지 이용자 중 케빈베이컨 수치가 가장 낮은 1인을 찾아보려고 합니다. 케빈 베이컨 수는 케빈 베이컨 게임을 할 때 모두가 밟은 단계의 합입니다.

예를 들어 BOJ에 5명의 사용자가 있고 1과 3, 1과 4, 2와 3, 3과 4, 4와 5가 친구인 경우를 생각해 보십시오.

1은 3~2까지 2레벨, 3~3까지 1레벨, 4~4까지 1레벨, 4~5까지 2레벨로 알 수 있습니다. 따라서 Kevin Bacon의 수는 2+1+1+2 = 6입니다.

2는 1~3까지는 2단계, 1~3까지는 2단계, 3~4까지는 2단계, 3~3까지는 3단계, 4~5까지는 알 수 있다. 따라서 Kevin Bacon의 수는 2+1+2+3 = 8입니다.

3은 1단계에서 1로, 1단계에서 2로, 1단계에서 4로, 4에서 5로 2단계로 알 수 있다. 따라서 Kevin Bacon의 수는 1+1+1+2 = 5입니다.

4는 1단계에서 1로, 2단계에서 2에서 3으로, 1단계에서 3으로, 1단계에서 5로 알 수 있다. Kevin Bacon의 숫자 4는 1+2+1+1 = 5입니다.

마지막으로 5는 1에서 4까지 2단계, 4에서 3단계, 3에서 2, 4에서 3까지 2단계, 4에서 1단계로 알 수 있습니다. Kevin Bacon의 숫자 5는 2+3+2+1 = 8입니다.

5명의 사용자 중 3과 4는 Kevin Bacon의 수가 가장 적은 사용자입니다.

BOJ 사용자 수와 그들의 친구 관계를 입력값으로 사용하여 Kevin Bacon이 가장 적은 사람을 찾는 프로그램을 작성하십시오.

기입

첫 번째 행은 사용자 수 N(2 ≤ N ≤ 100)과 친구 수 M(1 ≤ M ≤ 5,000)을 제공합니다. 우정 관계는 두 번째 행부터 M 행에 제공됩니다. 친구 관계는 A와 B로 구성되며 이는 A와 B가 친구라는 것을 의미합니다. A와 B가 친구라면 B와 A는 친구이고 A와 B는 결코 같지 않습니다. 우정은 두 배가 될 수 있으며 아무도 친구가 없습니다. 또한 모두가 친절합니다. 개인은 1부터 N까지 번호가 매겨지며 두 사람의 번호가 동일하지 않습니다.

누르다

첫 번째 줄은 BOJ 사용자 중 Kevin Bacon이 가장 적은 사람을 반환합니다. 그러한 사람이 여럿일 경우에는 가장 적은 사람을 부여한다.

설명

#include <iostream>
#include <vector>
#include <queue>
#include <cstring>
#define MAX 101
using namespace std;

vector<int> graph(MAX);
int dist(MAX)(MAX);

void bfs(int start) {
    bool visited(MAX);
    memset(visited, false, sizeof(visited));
    queue<int> q;
    q.push(start);
    visited(start) = true;
    int level = 0;

    while (!q.empty()) {
        int size = q.size();
        level++;
        for (int i = 0; i < size; i++) {
            int curr = q.front();
            q.pop();
            for (int j = 0; j < graph(curr).size(); j++) {
                int next = graph(curr)(j);
                if (!visited(next)) {
                    visited(next) = true;
                    q.push(next);
                    dist(start)(next) = level;
                }
            }
        }
    }
}

int main() 
{
    int n, m;
    cin >> n >> m;

    for (int i = 0; i < m; i++) {
        int u, v;
        cin >> u >> v;
        graph(u).push_back(v);
        graph(v).push_back(u);
    }

    for (int i = 1; i <= n; i++) {
        bfs(i);
    }

    int min_sum = MAX * MAX, ans = 0;
    for (int i = 1; i <= n; i++) {
        int sum = 0;
        for (int j = 1; j <= n; j++) {
            sum += dist(i)(j);
        }
        if (min_sum > sum) {
            min_sum = sum;
            ans = i;
        }
    }

    cout << ans;
}