백준 2610번 회의준비 - C++ 풀이

---

 

1. 각 사람이 리더일 때 의사전달시간의 최댓값은 플로이드 와샬 알고리즘을 사용하여 구할 수 있다.
2. 위원회는 그래프의 연결 요소와 같다.
3. DFS/BFS를 사용하여 각 위원회의 리더를 정한다.

 

1. 각 사람이 리더일 때 의사전달시간의 최대값은 플로이드 와샬 알고리즘을 사용하여 구할 수 있다.

 A가 리더일 때 B의 의사전달시간은 A와 B의 사이의 거리와 같다. 따라서 A가 리더일 때 의사전달시간의 최댓값은 나머지 모든 사람들과의 거리를 알면 구할 수 있다. 플로이드 와샬 알고리즘을 사용하여 모든 사람들에 대해 각 사람이 리더일 때의 의사전달시간의 최댓값을 구할 수 있다.

 

2. 위원회는 그래프의 연결 요소와 같다.

 위원회의 정의는 그래프의 연결요소와 같다. 따라서 K는 연결요소의 수와 같다.

 

3. DFS/BFS를 사용하여 각 위원회의 리더를 정한다.

 DFS/BFS를 사용하여 각 연결 요소들을 탐색한다. 탐색 과정에서 의사전달시간의 최댓값이 최소가 되는 리더를 정해야 한다. DFS/BFS 대신 분리집합을 사용할 수도 있다.

 

반응형

---

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

using namespace std;

const int INF = 987654321;

int N, M;
bool adjs[101][101], visit[101];
int dist[101][101], maxPassingTime[101];

void FloydWarshall() {
    for (int i=1; i<=N; i++) {
        for (int j=1; j<=N; j++) {
            if (i == j) dist[i][j] = 0;
            else if (adjs[i][j]) dist[i][j] = 1;
            else dist[i][j] = INF;
        }
    }
    
    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 calcPassingTime() {
    for (int i=1; i<=N; i++) {
        int maxTime = -1;
        
        for (int j=1; j<=N; j++) {
            if (dist[j][i] == INF) continue;
            maxTime = max(maxTime, dist[j][i]);
        }
        
        maxPassingTime[i] = maxTime;
    }
}

int DFS(int curr) {
    visit[curr] = true;
    
    int leader = curr;
    for (int next=1; next<=N; next++) {
        if (!adjs[curr][next] || visit[next]) continue;
        
        int cand = DFS(next);
        if (maxPassingTime[cand] < maxPassingTime[leader]) leader = cand;
    }
    
    return leader;
}

vector<int> pickLeaders() {
    vector<int> leaders;
    
    for (int i=1; i<=N; i++) {
        if (!visit[i]) leaders.push_back(DFS(i));
    }
    
    return leaders;
}

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL); cout.tie(NULL);
    
    cin >> N >> M;
    for (int i=0; i<M; i++) {
        int a, b;
        cin >> a >> b;
        adjs[a][b] = true;
        adjs[b][a] = true;
    }
    
    FloydWarshall();
    calcPassingTime();
    
    vector<int> leaders = pickLeaders();
    sort(leaders.begin(), leaders.end());
    
    cout << leaders.size() << "\n";
    for (auto leader: leaders) cout << leader << "\n";

    return 0;
}