(매일 BOJ) C++ 1389번 케빈 베이컨의 6단계 법칙

문제 요약

• N명의 사람과 M개의 친구 관계가 주어진다
• 친구 관계는 양방향이며, 한 사람과 다른 사람은 친구의 친구를 통해 연결될 수 있다
• 케빈 베이컨 수: 한 사람이 다른 모든 사람과 연결되는 최소 단계 수들의 합
• 케빈 베이컨 수가 가장 작은 사람의 번호를 출력

접근법

이 문제의 핵심은 모든 노드에서 다른 모든 노드까지의 최단 거리 합을 구하는 것이다

• A와 B가 직접 친구라면 거리는 1
• A의 친구의 친구라면 거리는 2
• 최단 거리 합이 가장 작은 노드를 출력

최단 거리 구하는 방법

• BFS 사용
  • BFS는 한 레벨씩 탐색하므로 최단 거리 계산에 최적
  • 시간 복잡도: O(N × (N+M)) → N ≤ 100 이므로 충분히 가능
• DFS 는 최단거리를 구할 수 없다 （DFS + 백트레킹 -> TLE）
• 플로이드 워셜 or BFS 를 사용해야 함

작성코드

#include <bits/stdc++.h>
using namespace std;

int N,M;
int BFS(vector<vector<int>> & graph, int start);

int main(void){
    ios::sync_with_stdio(false); cin.tie(0);
    cin >> N >> M;
    vector<vector<int>> graph(N+1);
    

    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; i++){
        sort(graph[i].begin(),graph[i].end());
    }

    int min = INT_MAX;
    int result;

    for(int i = 1; i <= N; i++){
        vector<bool> visited (N+1,false);
        int count = BFS(graph,i);

        if(count < min){
            min = count;
            result = i;
        }
    }

    cout << result;

}

int BFS (vector<vector<int>> & graph, int start) {
    vector<int> distance(N+1, -1);
    queue<int> q;

    distance[start] = 0;
    q.push(start);

    while(!q.empty()){
        int cur = q.front();
        q.pop();

        for( int next : graph[cur]){
            if(distance[next] == -1){
                distance[next] = distance[cur] + 1;
                q.push(next);
            }
        }
    }
    int sum = 0;
    for(int i = 1; i <= N; i++){
        sum += distance[i];
    }

    return sum;
}