백준 g5 2660 회장뽑기 c++

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

2660번: 회장뽑기

 

문제

한 사람이 있을 때, 

다른 모든 회원과 친구 -> 1점

다른 모든 회원과 친구 or 친구의 친구 -> 2점

...

이런 식으로 점수를 매겨서 회장 후보를 뽑는다.

회장 후보의 점수, 회장 후보의 수, 각 회장 후보의 번호를 차례대로 출력

 

이때 친구이면서 친친일 때는 친구로 생각해야 하며, 모두가 건너건너면 다 아는 사람임(다 연결된 하나의 그래프)

 

풀이

문제를 정리하면 가장 거리가 먼 친구와의 거리를 기준으로 점수를 구한다는 말

친구이면서 친친일 때는 친구로 생각해야하기 때문에 DFS보단 거리를 1씩 늘려가는 BFS가 더 코드 짜기 편하다.

 

수도 코드

1. adj 만들기
2. for 1번 후보부터 ~ N번 후보까지
	BFS 수행, vis[후보][j]에 거리 저장
    
   vis[cur] 중 max값이 바로 해당 후보의 점수가 된다.
   score[후보] = max(vis[cur])
   
3. score[i] 중 가장 낮은 거 골라서 출력

 

 

전체 코드

/*boj g5 2660 회장뽑기*/
#include <iostream>
#include <queue>
#include <vector>
#define MAXN 52
using namespace std;

int N;

vector<int> adj[MAXN];
int vis[MAXN][MAXN];
int score[MAXN];
int main(void) {
    ios::sync_with_stdio(0);
    cin.tie(0);
    cin >> N;
    while (1) {
        int x, y;
        cin >> x >> y;
        if (x == -1 && y == -1) break;
        adj[x].push_back(y);
        adj[y].push_back(x);
    }

    for (int i = 1; i <= N; i++) {
        queue<int> Q;
        vis[i][i] = 1;
        Q.push(i);

        while (!Q.empty()) {
            int cur = Q.front();
            Q.pop();

            for (int a : adj[cur]) {
                if (vis[i][a]) continue;

                vis[i][a] = vis[i][cur] + 1;
                Q.push(a);
            }
        }

        int mx = -1;
        for (int j = 1; j <= N; j++) {
            mx = max(mx, vis[i][j]);
        }
        score[i] = mx;
    }

    // 3. score[i] 중 가장 낮은 거 골라서 출력
    int mn = 999;
    for (int i = 1; i <= N; i++) {
        mn = min(mn, score[i]);
    }
    int num = 0;
    vector<int> ans;
    for (int i = 1; i <= N; i++) {
        if (score[i] == mn) {
            num++;
            ans.push_back(i);
        }
    }

    cout << mn - 1 << " " << num << "\n";
    for (int a : ans) {
        cout << a << " ";
    }
    cout << "\n";
}