[BOJ] 백준 2660 회장뽑기

출처: https://www.acmicpc.net/problem/2660

Approach

플로이드 와샬 (Floyd Warshall)을 이용할 수 있다.

플로이드 와샬 (Floyd Warshall)

---

#include <stdio.h>
const int MAX_N = 55;
int N, s, e, ans = MAX_N;
int dist[MAX_N][MAX_N], score[MAX_N];
int arr[MAX_N], acnt;

void input() {
    scanf("%d", &N);
    for (int i = 1; i <= N; ++i) {
        for (int j = 1; j <= N; ++j) {
            dist[i][j] = MAX_N;
        }
    }

    while (1) {
        scanf("%d %d", &s, &e);
        if (s < 0) break;
        dist[s][e] = dist[e][s] = 1;
    }
}

void Floyd() {
    int i, j, k;
    for (k = 1; k <= N; ++k) {
        for (i = 1; i <= N; ++i) {
            for (j = 1; j <= N; ++j) {
                if (dist[i][j] > dist[i][k] + dist[k][j]) {
                    dist[i][j] = dist[i][k] + dist[k][j];
                }
            }
        }
    }
}

void process() {
    int i, j;
    for (i = 1; i <= N; ++i) {
        for (j = 1; j <= N; ++j) {
            if (i != j) {
                if (score[i] < dist[i][j]) {
                    score[i] = dist[i][j];
                }
            }
        }
        if (ans > score[i]) ans = score[i];
    }
}

void output() {
    for (int i = 1; i <= N; ++i) {
        if (score[i] == ans) {
            arr[acnt++] = i;
        }
    }
    printf("%d %d\n", ans, acnt);
    for (int i = 0; i < acnt; ++i) {
        printf("%d ", arr[i]);
    }
    puts("");
}

int main() {
    // freopen("input.txt", "r", stdin);
    input();
    Floyd();
    process();
    output();
}