[BOJ #2610] 회의준비

시.도지역본선 초반 번호대의 문제다운 난이도로, Floyd-Warshall Algorithm (플로이드 와샬)을 이용해, 간단히 해결되는 문제입니다.

---

[Baekjoon Onine Judge]

#2610 회의준비

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

2004 한국정보올림피아드 시.도지역본선 중등부 3번

2004 한국정보올림피아드 시.도지역본선 고등부 3번

---

Problem Solving Strategy

다음과 같은 세 부분으로 나누어 생각을 해야지! 라는 생각이 떠오를 것입니다.

1. 모든 사람에 대해 플로이드 와샬 알고리즘을 돌린다.

2. 조건에 맞게 위원회를 구성한다.

3. 위원회의 대표를 찾는다.

1. 모든 사람에 대해 플로이드 와샬 알고리즘을 돌린다.

위원회의 대표를 찾는 과정에서, 플루이드 와샬 알고리즘이 필요하다는 것은 깨달았을 것입니다.

각각의 위원회에 대해 돌려도 되지만 코드가 불필요하게 길어지며, 모든 사람이 같은 위원회에 속하는 경우의 수도 존재하므로

처음에 그냥 모든 정점을 집어넣고 돌립니다.

for(int k=1;k<=N;k++)
    for(int i=1;i<=N;i++)
        for(int j=1;j<=N;j++)
            if(i!=j && dist[i][j]>dist[i][k]+dist[k][j]) dist[i][j]=dist[i][k]+dist[k][j];

2. 조건에 맞게 위원회를 구성한다.

3. 위원회의 대표를 찾는다.

굳이 각 위원회의 정보를 저장할 필요가 없으므로,  imsi로 그룹원을 저장하는 배열을 만들고 대표를 찾은 뒤, 각 그룹의 대표만 저장해도 됩니다. 본인은 반복문 탈출 조건을 N명의 사람을 모두 방문했을 때로 했습니다.

vSize=0; aSize=0;
while(vSize<N){ //방문한 사람 수가 N보다 작은 동안 반복문을 돕니다.
//임시 위원회를 구하는 과정입니다.
    emptyImsi();
    for(int i=1;i<=N;i++){
        if(imsisize==0 && visited[i]==0){ //임시 위원회의 한 사람을 구합니다.
            visited[i]=1; //방문자 처리
            imsisize++; vSize++;
            imsi[imsisize]=i;
            e=i;
        }
        if(imsisize!=0 && dist[e][i]!=INF){ //임시 위원회의 나머지 그룹원을 채워줍니다.
            visited[i]=1;
            imsisize++; vSize++;
            imsi[imsisize]=i;
        }
    }
 
//위원회의 대표를 찾는 과정입니다.
    s=1;//s는 일단 위원회의 1번을 대표라 가정합니다.
    int pe=INF;
    for(int i=1;i<=imsisize;i++)
    {    
        e=0;
        for(int j=1;j<=imsisize;j++)
        {
            if(e<=dist[imsi[i]][imsi[j]] && i!=j){
                e=dist[imsi[i]][imsi[j]];
            }
        }
        if(pe>=e){
            s=i;
            pe=e;
        }
    }
    aSize++; //출력할 답의 크기를 저장합니다.
    ans[aSize]=imsi[s]; //출력에 필요한 답만 저장해둡니다.
}

---

전체 코드 보기

블로그에 정리할 생각을 하지 않고 짰던 거라 변수명과 코드가 조금 지저분..해요 ㅠ-ㅠ

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77

#include<cstdio> #include<algorithm> #define INF 987654321 using namespace std;   int N, dist[101][101]; int imsi[101],imsisize,visited[101],vSize; int M,s,e; int ans[101],aSize;   void emptyImsi(){     for(int i=1;i<=N;i++) imsi[i]=0;     imsisize=0; }   int main(void){     imsisize=0;     scanf("%d",&N);     scanf("%d",&M);     for(int i=1;i<=N;i++)         for(int j=1;j<=N;j++)             dist[i][j]=INF;     for(int i=1;i<=M;i++){         scanf("%d %d",&s,&e);         dist[s][e]=1; dist[e][s]=1;     }       //fw algorithm//     for(int k=1;k<=N;k++)         for(int i=1;i<=N;i++)             for(int j=1;j<=N;j++)             if(i!=j && dist[i][j]>dist[i][k]+dist[k][j]) dist[i][j]=dist[i][k]+dist[k][j];       vSize=0; aSize=0;     while(vSize<N){     //임시 부분집합을 구하고         emptyImsi();         for(int i=1;i<=N;i++){             if(imsisize!=0 && dist[e][i]!=INF){                 visited[i]=1;                 imsisize++; vSize++;                 imsi[imsisize]=i;             }             if(imsisize==0 && visited[i]==0) {                 visited[i]=1;                 imsisize++; vSize++;                 imsi[imsisize]=i;                 e=i;             }         }              //부분그룹의 대표를 찾는다.         s=1;//s는 일단 부분그룹 1번이 대표!         int pe=INF;         for(int i=1;i<=imsisize;i++)         {                 e=0; //s는 임시 그룹 1번 여기서부터 e=MAX             for(int j=1;j<=imsisize;j++)             {                 if(e<=dist[imsi[i]][imsi[j]] && i!=j){                     e=dist[imsi[i]][imsi[j]];                 }             }             if(pe>=e){                 s=i;                 pe=e;             }         }         aSize++;         ans[aSize]=imsi[s];     }     sort(ans+1,ans+1+aSize);     printf("%d\n",aSize);     for(int i=1;i<=aSize;i++)         printf("%d\n",ans[i]);     return 0; }