[ BOJ 백준 1389번 - 케빈 베이컨의 6단계 법칙 ] 해설 및 코드

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

 

목적

각 정점간의 거리를 구하고, i정점에서 나머지 정점간 거리의 합이 최소인 i를 구하자.

 

접근법

1. 플로이드 와샬 알고리즘을 이용해 모든 정점간 거리를 구하자.

2. 다음, 거리합이 최소인 정점을 구한다.

 

 

#include<bits/stdc++.h>
#define f(i,r,l) for(int i=r;i<=l;++i)
#define INF 101
using namespace std;
 
int main() {
    ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    int n,m,s[INF][INF] = {};
    cin >> n>>m;
    f(i, 1, n) {
        f(j, 1, n)s[i][j] = INF;
        s[i][i] = 0;
    }
    while (m--) {
        int a, b; cin >> a >> b;
        s[a][b] = s[b][a] = 1;
    }
    
    f(k, 1, n)f(i, 1, n)f(j, 1, n){
        int tmp = s[i][k] + s[k][j];
        if (s[i][j] > tmp)s[i][j] = tmp;
    }
    
    int ans,mn = INF;
    f(i, 1, n) {
        int sum = 0;
        f(j, 1, n)sum += s[i][j];
        if (mn > sum) {
            ans = i;
            mn=sum;
        }
    }
    cout << ans;
    return 0;
}

문제 설명과 코드에 대한 피드백은 언제나 환영합니다.

 다양한 의견 댓글로 남겨주세요.