[Floyd] BOJ 2610 회의준비

문제 링크 : www.acmicpc.net/problem/2610

2610번: 회의준비

 

문제를 그래프의 관점에서 이해하면 다음과 같다.

① 서로 연결된 사람은 같은 위원회에 참석한다 = 그래프에서 연결된 노드들은 같은 위원회(그룹)로 취급한다.

② 효율적인 회의 진행을 위해 위원회의 수는 최대가 되어야 한다. = 그래프의 모든 정점에 대해 그룹화한다.

즉 그래프의 모든 정점에 대해 연결된 노드끼리 그룹(위원회)으로 묶은 후, 그룹의 대표 노드에 대해 다른 모든 노드에 대한 전파 시간을 계산한다.

전파 시간은 그래프에서 해당 노드까지의 최단거리를 의미한다. (모든 간선의 가중치를 1로 둔다.)

각 그룹별로 그룹의 의사전달시간(전파시간 합)이 최소가 되는, 즉 대표 이외의 모든 노드에 대한 최단거리 합이 최소가 되는 노드를 선택하는 문제이다.

그룹 내의 모든 노드에 대해 각 노드가 대표일 경우 다른 모든 노드에 대한 최단거리를 알아야 하므로, 플로이드-와샬 알고리즘을 적용한다.

[코드]

#define _CRT_SECURE_NO_WARNINGS
#include <iostream>
#include <vector>
#include <algorithm>
#include <memory.h>
 
#define INF 99999999
 
using namespace std;
int n, m;
vector<int> adj[101], heads, group;
int dist[101][101], gsize = 0;
bool visit[101];
 
void floyd() {
    for (int k = 1; k <= n; k++) {
        for (int i = 1; i <= n; i++) {
            for (int j = 1; j <= n; j++) {
                dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j]);
            }
        }
    }
}
 
void init() {
    int from, to;
    cin >> n;
    cin >> m;
 
    fill(&dist[0][0], &dist[100][100], INF);
    for (int i = 0; i < m; i++) {
        cin >> from >> to;
        adj[from].push_back(to);
        adj[to].push_back(from);
        dist[from][to] = 1;
        dist[to][from] = 1;
    }
 
    for (int i = 1; i <= n; i++) dist[i][i] = 0;
}
 
//그래프의 컴포넌트를 찾기 위한 탐색
void dfs(int node) {
    visit[node] = true;
    group.push_back(node);
    gsize++;
    for (int i = 0; i < adj[node].size(); i++) {
        if (!visit[adj[node][i]]) dfs(adj[node][i]);
    }
}
 
int gethead() {
    //floyd dist table에서 각 row의 dist값 총합이 가장 작은 노드가 대표이다.
    //단, 연결된 컴포넌트 내에서만 총합을 구한다.
    int distval = INF;
    int headpoint = -1;
    for (int i = 0; i < group.size(); i++) {
        int cur = group[i];
        int max = -1;
        for (int j = 0; j < group.size(); j++) 
            if (max < dist[cur][group[j]]) 
                max = dist[cur][group[j]];
        if (distval > max) { headpoint = cur; distval = max; }
    }
    return headpoint;
}
 
int main() {
    int g_cnt = 0;
    init();
    floyd();
 
    for (int i = 1; i <= n; i++) {
        if (!visit[i]) {
            group.clear();
            dfs(i); g_cnt++;
            int headpoint = gethead();
            if(headpoint != -1) heads.push_back(headpoint);
        }
    }
 
    printf("%d\n", g_cnt);
    sort(heads.begin(), heads.end());
    for (int i = 0; i < heads.size(); i++) printf("%d\n", heads[i]);
 
    return 0;
}