1389 - 케빈 베이컨의 6단계 법칙

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

무방향 그래프에서 모든 정점이 서로 얼마만큼 가까운지(최단경로)를 계산하는 문제이다.

모든 정점에 대해 각각 최단경로를 구해도 되지만,(다익스트라라면 $O(V(E+VlogV))$) 문제에서 조건이 2 ≤ N ≤ 100 이므로 플로이드 와샬 알고리즘$O(V^3)$을 사용해도 충분하고 소스가 깔끔하다.

소스 첨부

#include <cstdio>

#define INF 987654321

inline int min(int a, int b){return a<b?a:b;}

int main(){
    int i, j, k, n, m;
    int c[101][101];
    scanf("%d %d", &n, &m);
    
    for(i=0; i<n; ++i)
        for(j=0; j<n; ++j)
            c[i][j] = i==j?0:INF;
    
    for(i=0; i<m; ++i){
        int a, b;
        scanf("%d %d", &a, &b);
        c[a-1][b-1] = c[b-1][a-1] = 1;
    }
    
    for(k=0; k<n; ++k){
        for(i=0; i<n; ++i){
            for(j=0; j<n; ++j){
                if(c[i][k]+c[k][j] < c[i][j])
                    c[i][j] = c[i][k]+c[k][j];
            }
        }
    }
    
    int maxT = INF, thatPerson = 0;
    for(i=0; i<n; ++i){
        int bacon = 0;
        for(j=0; j<n; ++j)
            bacon += c[i][j]<INF?c[i][j]:0;
        if(bacon < maxT){
            maxT = bacon;
            thatPerson = i+1;
        }
    }
    printf("%d", thatPerson);
    
    return 0;
}