[백준 2610] 회의준비

2610번: 회의준비

문제에 "의사전달시간" 이라는 말이 나옵니다. 지문에도 나와있지만 한 사람에서 다른 사람으로 의견을 전달할 때 거치는 사람의 수를 의미하며 여러 경로가 있으면 최단 거리를 "의사전달시간"으로 잡습니다. 당장 이것만 봐도 최단 거리를 구하기 때문에 다익스트라가 먼저 떠오릅니다.

그런데 문제는

위원회에서 모든 참석자들의 의사전달시간 중 최댓값이 최소가 되도록 대표를 정하는 프로그램을 작성하세요.

최댓값이 최소?

얼핏보면 헷갈릴 수도 있는 지문입니다. 즉 이걸 두줄로 요약(?)을 해보면

• 최댓값: 어떤 위원회에 속한 한 위원이 다른 위원들에게 의견을 전달하기 위한 각 의사전달시간 중 가장 큰 값
• 최솟값: 각 위원들의 최대 의사전달시간 중 값이 가장 작은 값

어떤 위원의 의사전달시간 최대값을 구하기 위해 특정 위원의 시점에서 모든 위원들에게 가는 의사전달시간을 구해야 하고, 최솟값을 구하기 위해 모든 위원들의 최대 의사전달시간을 구해야 합니다. 즉, 위원들의 머릿수 만큼 다익스트라를 돌여야 하므로 결국에는 플로이드를 사용하면 됩니다.

대충 알고리즘을 짜보면 아래와 같습니다.

1. 플로이드를 돌려서 모든 위원들에 대한 의사전달시간 구하기
2. 위원들을 순회하여 위원회 생성
3. 각 위원들의 의사전달시간 최댓값 구하기.
4. 이렇게 구한 각 위원들의 의사전달시간 최댓값 중 최솟값 구하기.

코드 보기(C++)

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

using namespace std;

#define INF 987654321

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

    int N, M;
    cin >> N;
    cin >> M;
    vector<int> g[N+1], ans;
    bool visited[N+1];
    int floyd[N+1][N+1];

    // 초기화
    for(int i = 0; i <= N; i++) {
        visited[i] = false;
        for(int j = 0; j <= N; j++) {
            if(i == j) floyd[i][j] = 0;
            else floyd[i][j] = INF;
        }
    }

    for(int k = 0; k < M; k++) {
        int u, v;
        cin >> u >> v;
        g[u].push_back(v);
        g[v].push_back(u);
        floyd[u][v] = floyd[v][u] = 1;
    }
    
    // 각 위원의 의사전달시간 구하기
    for(int k = 1; k <= N; k++)
        for(int i = 1; i <= N; i++)
            for(int j = 1; j <= N; j++)
                floyd[i][j] = min(floyd[i][j], floyd[i][k] + floyd[k][j]);

    for(int x = 1; x <= N; x++) {
        if(!visited[x]) {
            // 위원회 생성
            vector<int> vs;
            queue<int> q;
            visited[x] = true;
            q.push(x);
            vs.push_back(x);
            while(!q.empty()) {
                int u = q.front(); q.pop();
                for(int i = 0; i < (int)g[u].size(); i++) {
                    int v = g[u][i];
                    if(!visited[v]) {
                        q.push(v);
                        vs.push_back(v);
                        visited[v] = true;
                    }
                }
            }
            sort(vs.begin(), vs.end());
            
            int res_vertex = vs[0], res_len = INF;
            for(int i = 0; i < (int)vs.size(); i++) {
                int u = vs[i];
                int max_len = 1;
                for(int j = 0; j < (int)vs.size(); j++) {
                    // 최댓값 구하기
                    int v = vs[j];
                    if(i == j) continue;
                    if(max_len < floyd[u][v]) {
                        max_len = floyd[u][v];
                    }
                }
                if(res_len > max_len) {
                    // 최솟값 구하기
                    res_vertex = u;
                    res_len = max_len;
                }
            }
            ans.push_back(res_vertex);
        }
    }
    cout << ans.size() << '\n';
    sort(ans.begin(), ans.end());
    for(int i = 0; i < (int)ans.size(); i++)
        cout << ans[i] << '\n';

    return 0;
}

 

ㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋ

분명히 맞게 짰는데 하도 틀려서 왜그런가 하고 봤더니 visited를 초기화를 하지 않았습니다. 그동안 파이썬만 계속 쓰다가 OpenCV공부하려고 C++을 3년만에 복귀하고 아직 C++ 문법을 적응 못하고 있습니다. 파이썬은 별도 처리 없이 배열을 그냥 list comprehension으로 초기화 하면 되니깐요.

    // 초기화
    for(int i = 0; i <= N; i++) {
        visited[i] = false;
        for(int j = 0; j <= N; j++) {
            if(i == j) floyd[i][j] = 0;
            else floyd[i][j] = INF;
        }
    }

초기화를 생활화 합시다.