[플로이드와샬] 1389번 케빈 베이컨의 6단계 법칙

이 문제는 플로이드 와샬 알고리즘을 적용시키는 엄청 기본적인 문제이다.

플로이드 와샬 알고리즘은 All pair Shortest Algorithm이다. 다시말해서, 어떤 점에서 다른 모든 점으로 가는 최단경로를 모두 구하는 문제이다. (어떤 쌍에 대해서도 최단경로를 알 수 있음)

3중 for문을 사용하기 때문에, 시간복잡도는 O(n^3)이다. 

이전 포스팅에서 자바로 구현한 플로이드와샬 알고리즘에 설명이 자세히 나와있으니 참고 바란다.

위의 문제에서는 1 4 와 같은 형식으로 사람1과 사람4가 친구라는것을 표현하고 있다. 이것을 알고리즘에서는 그냥 노드1 노드4의 가중치가 1이라고 표현해놓고 플로이드 와샬 알고리즘을 적용시키면 된다.

소스코드

#include <iostream>
#include <algorithm>
using namespace std;
int n, m;
int map[101][101];
int main() {
    cin >> n >> m;
    for (int i = 0; i < n; i++) 
        for (int j = 0; j < n; j++) 
            if(i!=j)map[i][j] = 99999999;
        
    for (int i = 0; i < m; i++) {
            int a, b; cin >> a >> b;
            a--;b--;
            map[a][b] =map[b][a]= 1;
    }
    for (int k = 0; k < n; k++) {
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                if (map[i][j] > map[i][k] + map[k][j])
                    map[i][j] = map[i][k] + map[k][j];
            }
        }
    }//플로이드 와샬 알고리즘 All pair Shortest Path 알고리즘.
 
    int MIN = 99999999;
    int result = 0;
    for (int i = 0; i < n; i++)
    {
        int temp = 0;
        for (int j = 0; j < n; j++) {
            temp += map[i][j];
        }
        if (MIN > temp) {
            MIN = temp;
            result = i;
        }
    }
    cout << result+1 << endl;
    return 0;
}