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

|

문제

내가 이해한 문제 내용

주어진 그래프에서 각 노드에서 다른 모든 노드까지의 최단경로를 구하여라.

접근 방식

플로이드를 사용해서 빠르게 구현하였다.

어려웠던 점 & 배운 점

std::fill함수를 공부할 수 있는 시간이었다.

시간복잡도

$O(N^3)$

코드

#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;

int adj[101][101];
int dp[101][101];

int n,m,v1,v2;

int main(void)
{
    scanf("%d%d",&n,&m);
    fill(adj[0],adj[0]+101*101,2e8);
    for(int i=0; i<m; i++){
        scanf("%d%d",&v1,&v2);
        adj[v1][v2]=1;
        adj[v2][v1]=1;
    }

    for(int k=1; k<=n; k++){
        for(int i=1; i<=n; i++){
            for(int j=1; j<=n; j++){
                if(i==j) continue;
                adj[i][j] = min(adj[i][j],adj[i][k]+adj[k][j]);
            }
        }
    }
    int _max = 2e8;
    int ans = 0;
    for(int i=1; i<=n; i++){
        int sum = 0;
        for(int j=1; j<=n; j++){
            if(i==j) continue;
            sum += adj[i][j];
        }
        if(_max>sum){
            _max = sum;
            ans = i;
        }
    }
    printf("%d",ans);
    return 0;
}