백준 2660번 회장 뽑기

 

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

2660번: 회장뽑기

풀이

각 회원을 정점으로, 친구사이를 가중치가 1인 간선으로 생각하면 회원의 점수는 그 회원과 가장 멀리 떨어진 정점과의 거리가 됩니다. 이를 구하려면 모든 회원 간의 관계 (모든 정점 사이의 거리) 를 알아야 하므로 플로이드-와샬 알고리즘을 적용하였습니다. 정점의 수가 N일 때 O(N^3)인 알고리즘이지만 회원의 수 (정점의 수) 가 최대 50이므로 사용할 수 있습니다.

코드

#include <iostream>
#define INF 55
using namespace std;
 
int main() {
    int dist[51][51], n, a, b, mm = INF, now_max, cnt;
    
    cin >> n;
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= n; j++)
            dist[i][j] = INF;
        dist[i][i] = 1;
    }
    
    while (true) {
        cin >> a >> b;
        if (a == -1 && b == -1)
            break;
        dist[a][b] = 1;
        dist[b][a] = 1;
    }
    
    for (int k = 1; k <= n; k++) {
        for (int i = 1; i <= n; i++) {
            for (int j = 1; j <= n; j++) {
                if (dist[i][j] > dist[i][k] + dist[k][j]) {
                    dist[i][j] = dist[i][k] + dist[k][j];
                    dist[j][i] = dist[i][k] + dist[k][j];
                }
            }
        }
    }
    
    cnt = 1;
    for (int i = 1; i <= n; i++) {
        now_max = 0;
        for (int j = 1; j <= n; j++) {
            if (dist[i][j] > now_max)
                now_max = dist[i][j];
        }
        if (now_max < mm) {
            mm = now_max;
            cnt = 1;
        }
        else if (now_max == mm)
            cnt++;
    }
    cout << mm << ' ' << cnt << endl;
    
    bool hubo;
    for (int i = 1; i <= n; i++) {
        hubo = true;
        for (int j = 1; j <= n; j++) {
            if (dist[i][j] > mm) {
                hubo = false;
                break;
            }
        }
        if (hubo)
            cout << i << ' ';
    }
    return 0;
}

사족

방학 프로젝트 준비하면서 공부한 내용인데 써먹어서 기분이 좋아요

 

플로이드-와샬 알고리즘에 관한 내용은 『C언어로 쉽게 풀어쓴 자료구조』의 해당 부분을 통해 공부했어요