[BOJ] 2660 회장뽑기 c++

문제 링크

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

핵심 알고리즘

-1 -1까지 인접리스트에 양방향으로 친구임을 표시한다.

dist배열에 얼마나 먼 친구인지에 대한 정보를 저장한다.

dist배열중에 가장 큰 값이 바로 그 회원의 점수이다.

해당 값을 score배열에 저장하고 그 점수 중 가장 작은 값을 ans에 구한다.

score배열을 1부터 n까지 돌면서 ans와 같은 값인 즉, 회장의 후보들을 v에 추가한다.

최종 코드

#include <iostream>
#include <vector>
#include <algorithm>
#include <string>
#include <queue>
#include <stack>
#include <tuple>
#include <set>
#include <unordered_map>
#include <map>
#include <cmath>
#include <sstream>
using namespace std;

vector<int> adj[51];
int dist[51];
int score[51];

int main(void) {
    ios::sync_with_stdio(false);
    cin.tie(NULL);

    int n;
    cin >> n;

    while (1) {
        int u, v;
        cin >> u >> v;

        if (u == -1 && v == -1)
            break;

        adj[u].push_back(v);
        adj[v].push_back(u);
    }

    int ans = 2500;
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= n; j++)
            dist[j] = -1;

        queue<int> q;
        q.push(i);
        dist[i] = 0;

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

            for (auto nxt : adj[cur]) {
                if (dist[nxt] >= 0)
                    continue;
                q.push(nxt);
                dist[nxt] = dist[cur] + 1;
            }
        }

        int big = 0;
        for (int j = 1; j <= n; j++)
            big = max(big, dist[j]);

        score[i] = big;
        ans = min(ans, score[i]);
    }

    vector<int> v;
    for (int i = 1; i <= n; i++)
        if (score[i] == ans)
            v.push_back(i);

    cout << ans << " " << v.size() << "\n";
    for (int i = 0; i < v.size(); i++)
        cout << v[i] << " ";
    
}