[C++]백준(BOJ) - 2660 회장뽑기(플로이드-와샬)

 

난이도 : 골V

알고리즘 유형 : 플로이드-와샬, bfs

풀이 방법 : 3중 for문(플로이드-와샬)

 

문제 링크

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

 

문제의 예시

월드컵 축구의 응원을 위한 모임에서 회장을 선출하려고 한다.

 

몇 사람을 통하면 모두가 서로 알 수 있다.

 -> 모두 연결되어있음

 

가까운 정도에 따라 점수를 받게 된다.

회장은 회원들 중에서 점수가 가장 작은 사람이 된다.

 -> 거리에 따른 정답 

 

A와 B가 친구면, 1점

A와 B가 친구고 B와 C가 친구면 A는 2점

이렇게 점수를 계산해 두루두루 친한 사람들 회장으로 뽑는 문제입니다. 

 -> 최단 거리라는 것을 알 수 있고, 모두 계산하기 때문에 플로이드로 풀 수 있다.

 -> 여기서 양방향 그래프라는 것도 알 수 있다. (B, A) == (A, B) 둘다 1

 

회장의 점수와 회장이 될 수 있는 모든 사람을 찾는 프로그램을 작성하시오.

첫째 줄에는 회장 후보의 점수와 후보의 수를 출력하고,

둘째 줄에는 회장 후보를 오름차순으로 모두 출력한다.

-> vector<int>를 sort 하는 것으로 구현했다.

 

 

3중 for문을 사용한 플로이드-와샬 구현 코드입니다.

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

using namespace std;

// 초기화값
const int inf = 1e9;

int n;
int board[52][52];

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);

    cin >> n;

    // 최대값 초기화
    for(int i = 1; i <= n; ++i)
        fill(board[i] + 1, board[i] + n + 1, inf);


    while(true)
    {
        int a, b; cin >> a >> b;
        
        if(a == -1 || b == -1)
            break;

        // 양방향 그래프
        board[a][b] = 1;
        board[b][a] = 1;
    }

    for(int i = 1; i <=n ;++i)
        board[i][i] = 0;

    // 플로이드-와샬
    for (int k = 1; k <= n; ++k)
        for (int i = 1; i <= n; ++i)
            for(int j = 1; j <= n; ++j)
                board[i][j] = min(board[i][j], board[i][k] + board[k][j]);

    int mx = inf * 2 + 1;
    
    vector<int> result;
    for (int i = 1; i <= n; ++i)
    {
        int cnt = -1;
        for (int j = 1; j <= n; ++j)
        {
            cnt = max(cnt, board[i][j]);
        }
        
        // i번이 가장 작다면 초기화
        if (mx > cnt)
        {
            mx = cnt;
            result.clear();
            result.push_back(i);
        }
        
        // i번이랑 최솟값이랑 같다면 추가
        else if(mx == cnt)
            result.push_back(i);
            
    }

    cout << mx << ' ' << result.size() << '\n';

    for(int i = 0; i < result.size(); ++i)
        cout << result[i] << ' ';

    return 0;
}