[C++] 백준 2660번 : 회장뽑기

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

문제

// 다른 모든 회원과 친구 -> 1점
// 다른 모든 회원이 친구 | 친구의 친구 -> 2점
// 다른 모든 회원이 친구 | 친구의 친구 | 친구의친구의 친구 => 3
// ...

// 회장 : 회원들 중 점수 가장 적음

 

그러니까, 한 다리를(depth) 건널 때마다 점수가 추가된다는 것이고,
그 depth가 가장 작은 수준에서 친구를 찾을 수 있는 사람이 회장이 된다는 것이다.

 

풀이

#include <bits/stdc++.h>
using namespace std;

// 다른 모든 회원과 친구 -> 1점
// 다른 모든 회원이 친구 | 친구의 친구 -> 2점
// 다른 모든 회원이 친구 | 친구의 친구 | 친구의친구의 친구 => 3

// 회장 : 회원들 중 점수 가장 적음
vector<vector<int>> graph(51);
int min_score = INT_MAX;
vector<int> ans_list;
int n;

void print_answer()
{
    cout << min_score << " " << ans_list.size() << '\n';
    for (auto e : ans_list)
    {
        cout << e << " ";
    }
}

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

    cin >> n;

    // 입력받고
    int s, e;

    while (true)
    {
        cin >> s >> e;
        if (s == -1 && e == -1)
        {
            break;
        }
        graph[s].push_back(e);
        graph[e].push_back(s);
    }

    // 채우기 : 시작정점(i) , 끝정점(j)
    for (int id = 1; id <= n; id++)
    {
        vector<bool> is_visited(n + 1, false);
        queue<pair<int, int>> v; // id, score
        int score = 0;
        v.push({id, score});
        is_visited[id] = true;

        while (!v.empty())
        {
            auto [node, point] = v.front();
            v.pop();

            for (auto next : graph[node])
            {
                if (!is_visited[next])
                {
                    v.push({next, point + 1});
                    is_visited[next] = true;
                }
            }

            score = point;
        }
        // cout << "id : " << id << " score : " << score << "\n";

        if (score < min_score)
        {
            ans_list.clear();
            min_score = score;
            ans_list.push_back(id);
        }
        else if (score == min_score)
        {
            ans_list.push_back(id);
        }
    }
    print_answer();
}