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

중요 지식

---

Floyd Warshall - 플로이드 와샬 알고리즘은 두 정점의 최단 경로를 구하는 알고리즘이다

코드

---

#include <iostream>

#define MAX 101
#define MIN(a,b) a<b ? a:b
#define INF 1000

using namespace std;

int N, M;
int map[MAX][MAX];

void initMap(){
    for(int i = 0; i <= N; i++){
        for(int j = 0; j <= N; j++){
            map[i][j] = INF;
            if(i == j) map[i][j] = 0;
        }
    }
}

void floyd(){
    for(int k = 0; k <= N; k++){
        for(int i = 0; i <= N; i++){
            for(int j = 0; j <= N; j++){
                map[i][j] = MIN(map[i][j], map[i][k] + map[k][j]);
            }
        }
    }
}

int main(){
    int minV = INF, minN;

    cin >> N >> M;

    initMap();

    for(int i = 0; i < M; i++){
        int a, b;
        cin >> a >> b;

        map[a][b] = map[b][a] = 1;
    }

    
    floyd();

    for(int i = 1; i <= N; i++){
        int sum = 0;
        for(int j = 1; j <= N; j++){
            sum += map[i][j];
        }

        if(minV > sum) {
            minV = sum;
            minN = i;
        }
    }

    cout << minN;

    return 0;
}

풀이

---

플로이드 알고리즘 외에도 다익스트라 알고리즘도 쓸 수 있지만 플로이드 알고리즘이 더 쉽고 간편하다