백준 1389 케빈 베이컨의 6단계 법칙 (C++)

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

플로이드-워셜을 이용한 문제이다. 플로이드-워셜을 구현하여 배열에 각 유저간의 최소 거리를 구하고 저장해주었다. 그 후 반복문을 돌며 각 유저간의 최소 거리를 더해주고 그 중 합이 가장 작은 유저를 출력해주었다.
간단한 문제였다. 플로이드-워셜은 모든 지점에서 다른 모든 지점간의 최소 거리를 구할 때 사용되고, 다익스트라는 한 지점에서 모든 지점간의 최소 거리를 구할 때 사용된다.

#include <iostream>
#include <algorithm>

#define INF 987654321

using namespace std;

int N, M, minSum = INF, res = 0;
int A[100][100];

void solution() {
    for (int k = 0; k < N; k++) {
        for (int i = 0; i < N; i++) {
            for (int j = 0; j < N; j++) {
                if (i == j) {
                    A[i][j] = 0;
                    continue;
                }

                A[i][j] = min(A[i][j], A[i][k] + A[k][j]);
            }
        }
    }

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

    for (int i = 0; i < N; i++) {
        int sum = 0;

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

        if (minSum > sum) {
            minSum = sum;
            res = i + 1;
        }
    }

    cout << res << "\n";
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL); cout.tie(NULL);

    cin >> N >> M;

    for (int i = 0; i < N; i++) {
        for (int j = 0; j < N; j++) {
            A[i][j] = INF;
        }
    }

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

        A[a - 1][b - 1] = 1;
        A[b - 1][a - 1] = 1;
    }

    solution();

    return 0;
}