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

#include <stdio.h>
 
int adj[105][105] = { 0 };
int dp[105][105] = { 0 };
int INF = 1000000;
 
int main() {
    int n, m;
    scanf("%d %d", &n, &m);
 
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= n; j++) {
            if(i!=j)
                dp[i][j] = INF;
        }
    }
 
    for (int i = 1; i <= m; i++) {
        int a, b;
        scanf("%d %d", &a, &b);
 
        adj[a][b] = 1;
        adj[b][a] = 1;
 
        dp[a][b] = 1;
        dp[b][a] = 1;
    }
 
    for (int k = 1; k <= n; k++) {
        for (int i = 1; i <= n; i++) {
            for (int j = 1; j <= n; j++) {
                if (dp[i][j] > dp[i][k] + dp[k][j]) {
                    dp[i][j] = dp[i][k] + dp[k][j];
                }
            }
        }
    }
 
    int rstSum = INF, idx = 0;
    for (int i = 1; i <= n; i++) {
        int sum = 0;
        for (int j = 1; j <= n; j++) {
            if (dp[i][j] != INF) {
                sum += dp[i][j];
            }
        }
        if (sum < rstSum) {
            idx = i;
            rstSum = sum;
        }
    }
 
    printf("%d", idx);
}