https://www.acmicpc.net/problem/1389
시간 2초, 메모리 128MB

input :

• N M (2 ≤ N ≤ 100, 1 ≤ M ≤ 5,000)
• A B

output :

• 첫째 줄에 BOJ의 유저 중에서 케빈 베이컨의 수가 가장 작은 사람을 출력한다. 그런 사람이 여러 명일 경우에는 번호가 가장 작은 사람을 출력

조건 :

• 임의의 두 사람이 최소 몇 단계 만에 이어질 수 있는지 계산하는 게임

• 케빈 베이컨 수는 모든 사람과 케빈 베이컨 게임을 했을 때, 나오는 단계의 합이다.

---

일반적인 그래프 탐색 문제이다. 모든 인원에 대해 탐색을 다 수행하는 것으로 문제를 해결할 수 있다.

다음 풀이

1. 두 사람이 이어진다.
2. 모든 사람과 게임을 수행
3. 최솟값을 찾아라

이어진다는 문장에서 그래프의 모양을 나타냄을 알 수 있다. 모든 사람과 수행하기 떄문에 모든 경우의 수를 다 찾으면 되고 최솟값이기에 도출된 값들을 비교해야 한다.

import sys
from collections import deque

n, m = map(int, sys.stdin.readline().split())
graph = [[] for _ in range(n + 1)]

for _ in range(m):
    a, b = map(int, sys.stdin.readline().split())
    graph[a].append(b)
    graph[b].append(a)

ans, cnt = float("inf"), float("inf")
for i in range(1, n + 1):
    visit, temp = [0] * (n + 1), 0
    q = deque([(i, 0)])
    visit[i] = 1

    while q:
        node, move = q.popleft()
        temp += move

        for next_node in graph[node]:
            if visit[next_node]:
                continue
            visit[next_node] = 1
            q.append((next_node, move + 1))

    if cnt > temp:
        ans, cnt = i, temp

print(ans)

#include "iostream"
#include "queue"
#include "vector"
#include "utility"

using std::cout; using std::cin;
using std::queue; using std::pair; using std::make_pair;
using std::vector;

int n, m, ans = 1e9, cnt = 1e9;
queue<pair<int, int>> q;
vector<vector<int>> graph;

void bfs(int idx){
    vector<int> visit(n + 1);
    int temp = 0;

    q.push(make_pair(idx, 0));
    visit[idx] = 1;

    while (!q.empty()){
        pair<int, int> node = q.front();
        q.pop();

        temp += node.second;
        for (int next_node : graph[node.first]) {
            if (visit[next_node])
                continue;
            visit[next_node] = 1;
            q.push(make_pair(next_node, node.second + 1));
        }
    }

    if (cnt > temp){
        ans = idx;
        cnt = temp;
    }
}

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

    for (int i = 0; i < n + 1; ++ i){
        vector<int> temp_graph;
        graph.push_back(temp_graph);
    }

    for (int i = 0; i < m; ++i){
        int a, b;
        cin >> a >> b;
        graph[a].push_back(b);
        graph[b].push_back(a);
    }

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

    cout << ans;
    return 0;
}