[백준] No.2610 - 회의준비 (C++, 플로이드-와샬)

문제

 

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

2610번: 회의준비

 

풀이

 

solved.ac 난이도: Gold 2

 

 

주어지는 그래프에서 간선을 통해 서로 도달 가능한 정점끼리 하나의 위원회(컴포넌트)를 이루게 하여 해결하는 플로이드-와샬 문제이다.

 

 

이 문제에서 플로이드-와샬(Flody-Warshall) 최단 경로 알고리즘이 적용되는 부분은 다음과 같다.

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

 

위원회는 서로 알고 있는 사람들끼리 모아두는 하나의 컴포넌트를 의미한다.

이때 위원회의 멤버는 자신이 알지 못하더라도 자신이 알고 있는 사람들이 알고 있는 관계라도 상관이 없다.

즉, 입력에서 주어지는 관계를 가진 사람의 쌍(u, v)을 간선으로 이어 주면 된다.

 

만약 두 정점이 서로 의견을 전달할 수 없다면, 이는 관계(간선)가 이어지지 못한 것으로 다른 위원회에 속한 다는 것을 알 수 있다.

플로이드 와샬 알고리즘은 두 정점 간의 도달 가능성까지 알 수 있는데,

두 정점(i, j) 사이의 최단 거리 dist[i][j]의 초기화 값인 INF가 플로이드 함수 실행 후에도 INF로 유지된다면

두 정점은 다른 정점을 경유 하더라도 이어질 수 없다.

따라서 다른 컴포넌트에 속함을 알 수 있다.

 

void FloydWarshall(){
  for(int k=1; k<=people_num ; ++k)
    for(int i=1; i<=people_num ; ++i)
      for(int j=1; j<=people_num ; ++j)
        dist[i][j] = min(dist[i][j], dist[i][k]+dist[k][j]);
}

 

 

이때 관계 간선의 가중치는 1로 설정하는데, 간선을 지난 다는 것은 다른 사람에게 의견을 전달했다는 의미로

대표에게 의견을 전달 할때 거치는 사람 수와 지나온 간선의 수는 동일하기 때문이다.

 

 

이제 문제는 같은 위원회(컴포넌트)에 속하는지 판별하는 부분이다.

이는 분리 집합 알고리즘으로도 해결할 수 있지만 간단히 BFS 스패닝 트리로 해결해보자.

 

다음과 같이 위원회가 구성된다면 다른 위원회 멤버(정점)끼리는 도달할 수 없으므로 dist[u][v]는 INF값을 나타낼 것이다.

 

 

따라서 방문한 정점은 visited표시를 하며 해당 정점에서 이동가능한 정점(dist값이 INF 미만인 정점)으로 BFS를 실행한다면 같은 위원회의 정점은 한 번의 BFS로 모두 순회할 수 있을 것이다.

그러므로 같은 BFS에서 방문이 되었다면 committee member로 vector배열에 저장해 주자.

 

bool visited[101], is_in_que[101];
int committee_order = 0;
vector<vector<int>> committee_member;
 
void FindCommitteeBFS(int start_idx){
  queue<int> q;
  vector<int> new_committee;  //이번에 생성하는 위원회의 멤버를 저장
  new_committee.push_back(start_idx);
 
  q.push(start_idx);
  is_in_que[start_idx] = true;
  visited[start_idx] =true;
 
  int idx;
  while(!q.empty()){
    idx = q.front();
    q.pop();
    visited[idx] = true;
 
    for(int i=1; i<= people_num ; ++i){
      //방문하지 않았거나 큐에 삽입되지 않은 정점만 확인
      if(!visited[i] && !is_in_que[i])
        if(dist[idx][i] < INF){ //dist가 INF라면 idx와 i정점은 서로 도달 불가
          q.push(i);
          is_in_que[i] = true;
          new_committee.push_back(i); //위원회 멤버로 추가
        }
 
    }
  }
 
  committee_member.push_back(new_committee); //새로운 위원회를 삽입
}

 

 

모든 위원회의 멤버를 구했다면 플로이드로 구한 최단 거리 정보를 이용하여 멤버들에서 대표를 정해주면 된다.

 

  for(int i=1; i<=people_num ; ++i)
    //관계가 이어지는 사람끼리만 위원회를 만듬
    if(!visited[i]){
      FindCommitteeBFS(i);
      ++committee_order;
    }
 
  vector<int> representives;
  int now_idx, next_idx;
  for(int k=0; k<committee_order ; ++k){
    pair<int,int> represent_info(0,INF);   //K번째 위원회의 대표의 정보
 
    for(int i=0; i<committee_member[k].size() ; ++i){
      int max_dist = 0; //now_idx와 다른 정점들 사이의 가장 먼 거리를 저장
      now_idx = committee_member[k][i];
 
      for(int j=0; j<committee_member[k].size() ; ++j){
        next_idx =committee_member[k][j];
        max_dist = max(dist[now_idx][next_idx], max_dist);
      }
 
      //현재 대표의 의사 전달시간 보다 작은 경우 새로운 대표로 선택
      if(max_dist < represent_info.second)  
        represent_info = {now_idx, max_dist};
    }
    representives.push_back(represent_info.first);
  }
 
  sort(representives.begin(), representives.end());

 

 

 

 

코드