[C/C++] 백준 #2660 회장뽑기(플로이드-워샬)

#2660 문제는 복잡하게 설명을 했지만, 결국 모든 간선의 웨이트가 1인 그래프에서 경로의 합 중 가장 적은 경로의 합을 가진 사람을 찾는 문제입니다.

 

chairman election

 

모든 그래프의 노드들과 노드들간의 경로를 구하기 위해서는 가장 적합한 그래프 알고리즘은 플로이드-워샬 알고리즘입니다.  여기에는 선택의 여지가 없는데, 다음에 회장 후보들을 선택하기 위해서는 나름대로의 알고리즘을 구성해서 해야 합니다.

 

플로이드-워샬 알고리즘이 \(O(N^3)\)이기 때문에 플로이드-워샬 알고리즘의 결과를 순회하는 것으로 작성한다면, 해당 시간복잡도가 \(O(N^2)\)이므로 시간복잡도상으로는 큰 문제가 없습니다.

 

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

 

1. **입력받기 및 초기화**:
    - `n`: 회원의 수를 입력받습니다.
    - `d[51][51]`: 각 회원들 간의 거리를 저장하는 2차원 배열입니다. 초기값을 `0xff`로 설정하여 큰 값으로 초기화합니다.
    - `v[50]`: 회장 후보를 저장하는 배열입니다.

    int n, a, b;
    unsigned char d[51][51], v[50];
    scanf("%d", &n);
    memset(d, 0xff, sizeof(d));

2. **관계 입력받기**:
    - 회원들 간의 관계를 입력받아 `d` 배열에 저장합니다. 두 회원 `a`, `b`가 서로 친구 관계일 때 `d[a][b]`와 `d[b][a]`를 1로 설정합니다.

    for( ; ; )
    {
        scanf("%d%d",&a,&b);
        if(a==-1) break;
        d[a][b]=1;
        d[b][a]=1;
    }

3. **플로이드-와샬 알고리즘**:
    - 모든 노드에서 모든 노드로의 최단 거리를 계산합니다. 이를 통해 각 회원들 간의 최단 거리를 구합니다.

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

4. **회장 후보 계산**:
    - 각 회원의 최대 거리를 계산하여 가장 작은 최대 거리를 가진 회원들을 찾습니다.

    int min=255, cnt=0;
    for(int i=1;i<=n;i++)
    {
        int max=0;
        for(int j=1;j<=n;j++)
        {
            if(i==j) continue;
            if(d[i][j]>max) max=d[i][j];
        }
        if(min>max) { min=max; cnt=1; v[0]=i;}
        else if(min==max) v[cnt++]=i;
    }

5. **결과 출력**:
    - 회장의 점수와 후보 수, 후보 번호들을 출력합니다.

    printf("%d %d\n", min, cnt);
    for(int i=0;i<cnt;i++) printf("%d ", v[i]);
    putchar('\n');

 

### 상세 설명

- **거리 배열 초기화**: `memset(d, 0xff, sizeof(d))`는 배열을 큰 값으로 초기화하여 초기 상태에서 모든 거리가 무한대임을 나타냅니다. 이는 플로이드-와샬 알고리즘에서 실제 거리를 업데이트하기 전까지의 상태를 반영합니다.
- **플로이드-와샬 알고리즘**: 이 알고리즘은 모든 정점 쌍 간의 최단 거리를 계산하는 데 사용됩니다. 3중 for 루프를 사용하여 각 노드를 중간 노드로 고려하여 최단 거리를 업데이트합니다.
- **회장 후보 선택**: 각 회원의 최대 거리를 계산하여 가장 작은 최대 거리를 가진 회원들을 회장 후보로 선택합니다.

그래서 완성된 소스입니다.

//------------------------------------------------
//    baekjoon #2660
//        - by Aubrey Choi
//        - created at 2019-08-05
//------------------------------------------------
#include <stdio.h>
#include <memory.h>

int main()
{
    int n, a, b;
    unsigned char d[51][51], v[50];
    scanf("%d", &n);
    memset(d, 0xff, sizeof(d));
    for( ; ; )
    {
        scanf("%d%d",&a,&b);
        if(a==-1) break;
        d[a][b]=1;
        d[b][a]=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) continue;
                int min = d[i][j], s = d[i][k]+d[k][j];
                if(min > s) min = s;
                d[i][j]=min;
            }
        }
    }
    int min=255, cnt=0;
    for(int i=1;i<=n;i++)
    {
        int max=0;
        for(int j=1;j<=n;j++)
        {
            if(i==j) continue;
            if(d[i][j]>max) max=d[i][j];
        }
        if(min>max) { min=max; cnt=1; v[0]=i;}
        else if(min==max) v[cnt++]=i;
    }
    printf("%d %d\n", min, cnt);
    for(int i=0;i<cnt;i++) printf("%d ", v[i]);
    putchar('\n');
    return 0;
}