백준 1389 : 케빈 베이컨의 6단계 법칙[C++]

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

 

결국 그래프에서 한 정점으로부터 다른 정점까지의 최단거리를 모두 구해서 더해주겠다는 뜻

= 최단경로 알고리즘

= 그중에서도 모든 정점간 최단거리를 구할 수 있는 플로이드워셜을 쓰면 된다.

 

플로이드-워셜은 가능한 모든 두 정점 간 조합에 대한 최단경로를 구하는 ASP(All-Pairs) 알고리즘으로, 두 정점 사이의 최단경로에 포함될 수 있는 모든 정점을 고려한다.

정점 V개 간선 E개에서 O(V^3)의 복잡도를 가진다.

모든 정점 사이의 최단경로를 구해야할 때는 다익스트라보다 효율적인 부분이 있다.

 

각 정점을 중간 정점으로 하여, 시작과 끝점에서 해당 정점을 지나는 것과 지나지 않는 것 중 더 짧은 거리를 선택해 그것을 최단경로로 한다. 중간/시작/끝점을 기준으로 삼중 반복문을 돈다.

void floyd(int n, vector<vector<int>>&graph){
    for(int k=1;k<=n;k++){ //중간
        for(int i=1;i<=n;i++){ //시작
            for(int j=1;j<=n;j++){ //끝
                int cost = graph[i][k] + graph[k][j];
                graph[i][j] = min(cost, graph[i][j]);
            }
        }
    }
}

 

전체 코드

메인이 좀 더럽다

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

void floyd(int n, vector<vector<int>>&graph){
    for(int k=1;k<=n;k++){ //중간
        for(int i=1;i<=n;i++){ //시작
            for(int j=1;j<=n;j++){ //끝
                int cost = graph[i][k] + graph[k][j];
                graph[i][j] = min(cost, graph[i][j]);
            }
        }
    }
}

int main()
{
    int n, m;
    cin >> n >> m;
    vector<vector<int>> graph(n+1, vector<int>(n+1, 1e6));
    for(int i=1;i<=n;i++){ //시작과 끝이 자기자신일 경우 0으로
        graph[i][i] = 0;
    }
    
    int a, b;
    vector<int> kevin_arr(n+1, 0);
    
    while(m--){
        cin >> a >> b;
        graph[a][b] = 1; //무방향 그래프이므로 둘다 같게
        graph[b][a] = 1;
    }
    
    floyd(n, graph); //플로이드-워셜 실행
    
    //케빈베이컨 수 구하기
    for(int i=1;i<=n;i++){
        int kevin = 0;
        for(int j=1;j<=n;j++){
            kevin += graph[i][j]; //i를 시작으로 하여 다른 모든 정점까지의 최단거리 더함
        }
        kevin_arr[i]=kevin;
    }
    
    int min_kevin = 1e6;
    int min_index = 0;
    for(int i=1;i<=n;i++){
        if (kevin_arr[i] < min_kevin) { //최소 케빈베이컨수 찾기
            min_kevin = kevin_arr[i];
            min_index = i; // 인덱스 업데이트
        }
    }
    cout << min_index;

    return 0;
}