[BOJ 1389] 케빈 베이컨의 6단계 법칙(C++)

케빈 베이컨의 6단계 법칙(Silver 1)

문제

전체 문제 보기

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

접근법

모든 사람에 대해서 각 사람들까지 관계 단계를 모두 계산해야 합니다. 이럴 경우 플로이드 워셜 알고리즘을 사용할 수 있습니다. 모든 사람들 관계에 대한 2차원 테이블을 만듭니다. 그리고 플로이드 워셜 알고리즘을 활용하여 관계의 최단 거리를 구합니다. 이 거리들의 합이 바로 케빈 베이컨의 수가 됩니다. 이 수가 가장 작은 사람을 출력하면 정답을 구할 수 있습니다.

전체 구현 코드

#include <iostream>
#include <vector>
#define endl '\n'
using namespace std;

const int INF = 200'000;
int main() {
    // 입출력 성능 향상을 위한 설정
    ios_base::sync_with_stdio(false);
    cout.tie(NULL);
    cin.tie(NULL);

    int N, M; //  유저의 수 N (2 ≤ N ≤ 100)과 친구 관계의 수 M (1 ≤ M ≤ 5,000)
    cin >> N >> M;
    vector<vector<int>> table(N);
    for (auto& row : table)
    {
        row.resize(N, INF);
    }
    for (int i = 0; i < N; ++i)
    {
        table[i][i] = 0;
    }
    while (M--)
    {
        int a, b;
        cin >> a >> b;
        table[a-1][b-1] = 1;
        table[b-1][a-1] = 1;
    }

    // 플로이드 워샬
    for (int k = 0; k < N; ++k)
    {
        for (int i = 0; i < N; ++i)
        {
            for (int j = 0; j < N; ++j)
            {
                if (table[i][j] > table[i][k] + table[k][j])
                {
                    table[i][j] = table[i][k] + table[k][j];
                    table[j][i] = table[i][j];
                }
            }
        }
    }

    // 케빈 베이컨 수가 가장 작은 사람 탐색
    int sum{}, minSum{INF}, answer{};

    for (int i = 0; i < N; ++i)
    {
        sum = 0;
        for (int j = 0; j < N; ++j)
        {
            sum += table[i][j];
        }
        if (sum < minSum)
        {
            answer = i + 1;
            minSum = sum;
        }
    }

    cout << answer;
    return 0;
}

성능 평가

플로이드 워셜 알고리즘의 시간복잡도는 \(O(N^3)\)입니다. 공간 복잡도는 전체 관계를 저장하기 위한 2차원 배열이 요구되기 때문에 \(O(N^2)\)만큼의 공간이 필요합니다.