백준, BOJ, 1389번, 케빈 베이컨의 6단계 법칙 : C++ [CPP]

 

플로이드 알고리즘 적용해서 풀었다.

 

크리스마스 쉬고와서 그런지.. 머리가 하나도 안돌아간다.

 

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

 

---

 

#맞는 풀이

#include <iostream>
#include <algorithm>
#include <climits>
#include <vector>

#define INF 123456789

using namespace std;

int cost[105][105];

int N,M;

int main(){
    cin >> N >> M;
    for(int i = 1; i<=N; i++){
        fill(cost[i], cost[i]+(N+1), INF);
    }
    for(int i = 0; i<M; i++){
        int from, to;
        cin >> from >> to;
        cost[from][to] = 1;
        cost[to][from] = 1;
    }
    //자기 자신으로 돌아오는 경로도 있어서 초기화 시켜줘야함 최단 경로 0으로 
    for (int i = 1; i <= N; i++) cost[i][i] = 0;

    
    
    for(int k = 1; k<=N; k++){
        for(int i = 1; i<=N; i++){
            for(int j = 1; j<=N; j++){
                cost[i][j] = min(cost[i][k]+cost[k][j], cost[i][j]);
            }
        }
    }
    vector <pair<int,int>> vec;
    int ans = INF;
    
    for(int i = 1; i<=N; i++){
        int tot = 0;
        for(int j = 1; j<=N; j++){
            tot += cost[i][j];
        }
        if(ans > tot){
            ans = tot;
            vec.push_back({tot,i});
        }
    }
    sort(vec.begin(), vec.end());
    
    
    cout << vec[0].second;
    
    return 0;
}

 

처음에.. cost를 모두 INF로 해주고

자기 자신은 경로를 0으로 설정해주고

K를 거쳐서 갈 수 있는 경로가 있다면 갱신해주고

여러 개가 있다면 cost가 갱신될 때마다 저장한 것 중 

최소 코스트이면서 최소인 숫자를 정렬해서 출력한다.