백준 2660 회장뽑기 (C++)

2660번: 회장뽑기

플로이드-워셜을 이용하는 문제이다. 먼저 친구 관계를 입력받을 때 이를 배열에 저장해주었다. 친구는 양방향이므로 A[a][b]와 A[b][a] 둘 다 1을 저장해주었다. 그 후 플로이드 워셜 알고리즘을 통해 각각의 최단 거리를 구해주었다. 이 때 자기자신은 0을 저장해주어야 한다. 그 후 점수를 구한 후 점수에 해당하는 회장 후보들을 오름차순으로 출력해주었다. 어렵지 않게 풀 수 있었던 문제였다. 모든 쌍 간의 최단 거리를 구하고 싶을 때는 플로이드 워셜 알고리즘을 사용한다는 것을 기억해두자.

#include <iostream>
#include <algorithm>
#include <vector>

#define INF 987654321

using namespace std;

int N;
int A[50][50];
vector<int> result;

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]);
            }
        }
    }

    int minv = INF;
    for (int i = 0; i < N; i++) {
        int score = 0;

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

        result.push_back(score);
        minv = min(minv, score);
    }

    cout << minv << " " << count(result.begin(), result.end(), minv) << "\n";
    for (int i = 0; i < N; i++) {
        if (result[i] == minv) cout << i + 1 << " ";
    }
}

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

    cin >> N;

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

    while (1) {
        int a, b;

        cin >> a >> b;

        if (a == -1 && b == -1) break;

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

    solution();

    return 0;
}