1389번: 케빈 베이컨의 6단계 법칙(20분)

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

구현 아이디어 5분 구현 15분

풀이

플로이드-와샬.

#define _CRT_SECURE_NO_WARNINGS
#include <iostream>
#include <string>
#include <vector>
#include <algorithm>

using namespace std;

vector<vector<int>> Check(101, vector<int>(101, 2147000000));
int N{}, M{};

void Func()
{
    // i번 정점을 거쳐가는 경우
    for (int k = 1; k <= N; ++k)
    {
        for (int i = 1; i <= N; ++i)
        {
            for (int j = 1; j <= N; ++j)
            {
                if (Check[i][k] == 2147000000 || Check[k][j] == 2147000000) continue;
                // 점화식
                Check[i][j] = min(
                    Check[i][j],
                    Check[i][k] + Check[k][j]
                );
            }
        }
    }
}

int main() {
    scanf("%d %d", &N, &M);

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

    for (int i = 0; i < M; ++i)
    {
        int Friend1{}, Friend2{};
        scanf("%d %d", &Friend1, &Friend2);
        Check[Friend1][Friend2] = 1;
        Check[Friend2][Friend1] = 1;
    }

    Func();

    int MinimumSum = 2147000000;
    int Result = -1;
    for (int i = 1; i <= N; ++i)
    {
        int Sum{};
        for (int j = 1; j <= N; ++j)
        {
            Sum += Check[i][j];
        }

        if (MinimumSum > Sum)
        {
            MinimumSum = Sum;
            Result = i;
        }
    }

    printf("%d\n", Result);

    return 0;
}