백준 2610번 회의준비[골드 2][C++]

1. 개요 

 안녕하세요. 이 문제의 유형은 플로이드-와샬에 유니온파인드를 곁들인 응용문제였습니다. 구현 자체는 쉬운데 문제에 함정이 있어 주의해야 합니다. 그래프는 무방향 비연결 그래프가 주어지는데 각 컴포넌트마다 자동으로 문제에서 설명한 위원회가 됩니다. 이제 문제 풀이 로직 구현을 설명해 보겠습니다.

 

2. 문제 풀이

2 - 1. 의사전달시간 구하기

 문제에서 요구한 내용을 구현하기 위해서는 의사전달시간이 최소가 되어야 합니다. 그리고 인접행렬만 주어져있을 때에는 각 위원회에서 누가 대표가 되는지 모르기 때문에 모든 정점에서의 최단의사전달시간을 구해야 합니다. 정점의 개수가 최대 100개이므로 플로이드-와샬을 수행해도 시간복잡도에 문제는 없습니다. 따라서 플로이드-와샬을 수행하시면 됩니다.

 

2 - 2. 위원회에 속한 정점 분리하기

 플로이드-와샬로 구한 거리 배열에서는 d[i][j] = INF이면 (i , j)는 서로 다른 위원회에 속한 정점임을 알 수 있습니다. 하지만 위원회의 개수를 구할 때에는 유니온 파인드를 사용했습니다. d[i][j] != INF이면 union을 진행하면서 위원회를 분류했습니다.

 

2- 3. 대표 구하기

 loop를 돌면서 의사전달시간의 최댓값 중 최소가 되는 대표 정점을 아무거나 하나 찍어 저장합니다. 이때 pair <>를 사용하면 쉽게 구할 수 있습니다. 이렇게 대표를 구한 다음 배열에 대표 정점을 모두 삽입하고 정렬하여 출력하면 풀이할 수 있습니다.

 

3. 코드

#include <bits/stdc++.h>
using namespace std;
typedef long long ll; typedef unsigned long long ull; typedef pair<int,int> pi; typedef pair<ll, ll> pl;
typedef tuple<int, int, int> ti; typedef tuple<ll, ll, ll> tl; typedef vector<int> vi; typedef vector<ll> vl;
typedef vector<pi> vpi; typedef vector<pl> vpl; typedef vector<ti> vti; typedef vector<tl> vtl;
typedef vector<string> vs; typedef vector<bool> vb; typedef queue<int> qi; typedef queue<ll> ql;
typedef queue<pi> qpi; typedef queue<pl> qpl; typedef queue<ti> qti; typedef queue<tl> qtl;
#define fastio(x, y) cin.tie((x))->sync_with_stdio((y))
#define X first
#define Y second
#define pb push_back
#define sz(x) (int((x).size()))
#define all(x) (x).begin(), (x).end()
#define rall(x) (x).rbegin(), (x).rend()
const char nl = '\n';

const int INF = 0x3f3f3f3f;

vi p(105, -1);

int find(int x) {
    return (p[x] < 0 ? x : p[x] = find(p[x]));
}

void merge(int x, int y) {
    x = find(x);
    y = find(y);
    
    if(x == y) {
        return;
    }

    if(--p[x] > p[y]) {
        swap(x, y);
    }

    p[y] = x;
}

int n, m;
int d[105][105];

int main() {
    fastio(nullptr, false);
    
    memset(d, 0x3f, sizeof(d));

    cin >> n >> m;
    while(m--) {
        int u, v;
        cin >> u >> v;
        d[u][v] = 1;
        d[v][u] = 1;
    }

    for(int i = 1; i <= n; i++) {
        d[i][i] = 0;
    }

    for(int k = 1; k <= n; k++) {
        for(int i = 1; i <= n; i++) {
            for(int j = 1; j <= n; j++) {
                d[i][j] = min(d[i][j], d[i][k] + d[k][j]);            
            }
        }
    }

    for(int i = 1; i <= n; i++) {
        for(int j = 1; j <= n; j++) {
            if(d[i][j] != INF) {
                merge(i, j);
            }
        }
    }

    vi group;
    for(int i = 1; i <= n; i++) {
        group.pb(find(i));
    }
    sort(all(group));
    group.erase(unique(all(group)), group.end());

    vpi ans(*max_element(all(group)) + 1, {INF, n + 1});
    for(int i = 1; i <= n; i++) {
        int mx = 0;
        for(int j = 1; j <= n; j++) {
            mx = max(mx, (d[i][j] != INF) * d[i][j]);
        }
        ans[find(i)] = min(ans[find(i)], {mx, i});
    }

    vi tmp;
    for(auto x : group) {
        tmp.pb(ans[find(x)].Y);
    }

    sort(all(tmp));
    cout << sz(group) << nl;
    for(auto x : tmp) {
        cout << x << nl;
    }
}

 

4. 제출 결과