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

  16 Nov 2019


Problem

Image

Concept & Idea

for(int i=1; i<=n; i++) {
for(int j=1; j<=n; j++) {
for(int k=1; k<=n; k++) {
if(dp[j][k]>dp[j][i]+dp[i][k]) {
dp[j][k]=dp[j][i]+dp[i][k];
dp[k][j]=dp[j][i]+dp[i][k];
}
}
}
}

코드의 핵심이 되는 플로이드 와샬 코드 부분이다.
간단한 문제이기 때문에 자세한 설명은 생략하도록 하겠다

Code

#include <iostream>
#include <vector>
#include <queue>
using namespace std;
int n,m;
int dp[101][101];
int main(){
    cin>>n>>m;
    for(int i=1; i<=n; i++) {
        for(int j=1; j<=n; j++) {
            if(i==j) {
                dp[i][j]=0;
            } else {
                dp[i][j]=102;
            }
        }
    }
    for(int i=0; i<m; i++) {
        int a,b;
        cin>>a>>b;
        dp[a][b]=1;
        dp[b][a]=1;
    }
    for(int i=1; i<=n; i++) {
        for(int j=1; j<=n; j++) {
            for(int k=1; k<=n; k++) {
                if(dp[j][k]>dp[j][i]+dp[i][k]) {
                    dp[j][k]=dp[j][i]+dp[i][k];
                    dp[k][j]=dp[j][i]+dp[i][k];
                }
            }
        }
    }
    int cnt=5000000; int res=0;
    for(int i=1; i<=n; i++) {
        int temp=0;
        for(int j=1; j<=n; j++) {
            if(i!=j)
                temp+=dp[i][j];
        }
        if(cnt>temp) {
            cnt=temp;
            res=i;
        }
    }
    cout<<res<<endl;
}

Fealing

이 문제 유형은 플로이드 워셜 알고리즘, DFS, BFS를 이용해서 해결할 수 있다. BFS와 DFS로 해결하려고 했는데,, 뭔가 시간초과가 날 수도 있다고 생각해서 플로이드 와샬 알고리즘을 이용해서 해결하였다. 중간에 플로이드 와샬 알고리즘이 헷갈려서.. 배열 인덱스값을 잘 못 넣었는데,, 주의하자.

Check out this code in Victoria’s Gist. Please Comment my code in this link.

...