[백준] 2660번 회장뽑기

문제: 2660번: 회장뽑기

basic-algo-lecture/workbook/0x18.md at master · encrypted-def/basic-algo-lecture

basic-algo-lecture/workbook/0x18.md at master · encrypted-def/basic-algo-lecture

 

//#include <bits/stdc++.h>
#include <iostream>
#include <vector>
#include <algorithm>
#include <climits>
#include <string>
#include <queue>
#include <set>
#include <iomanip>
#include <string.h>
#include <sstream>
#include <tuple>
#include <regex>
#include <stack>
#include <map>

using namespace std;

vector<vector<int>> linked;
vector<bool> visits;

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

    int n; // 회원의 수
    cin >> n;
    linked = vector<vector<int>>(n + 1); // 0번 인덱스 안 써
    visits = vector<bool>(n + 1);

    while (true) {
        int num1, num2;
        cin >> num1 >> num2;

        if (num1 == -1 && num2 == -1) break;

        linked[num1].push_back(num2);
        linked[num2].push_back(num1);
    }

    int totalMin = INT_MAX;
    vector<int> answer;
    queue<pair<int, int>> nexts;
    for (int i = 1; i <= n; i++) {
        nexts.push({ i, 0 });
        visits[i] = true;

        int curMax = 0;
        while (!nexts.empty()) {
            pair<int, int> cur = nexts.front(); nexts.pop();

            curMax = curMax < cur.second ? cur.second : curMax;

            for (int next : linked[cur.first]) {
                if (visits[next] == true) continue;

                nexts.push({ next, cur.second + 1 });
                visits[next] = true;
            }
        }
        if (curMax <= totalMin) {
            if (curMax < totalMin) {
                answer.clear();
            }
            answer.push_back(i);
            totalMin = curMax;
        }
        visits = vector<bool>(n + 1);
    }
    cout << totalMin << " " << answer.size() << "\n";
    sort(answer.begin(), answer.end());
    for (int ans : answer) {
        cout << ans << " ";
    }
   
    return 0;
}

 

" 입력의 첫째 줄에는 회원의 수가 있다. 단, 회원의 수는 50명을 넘지 않는다. 둘째 줄 이후로는 한 줄에 두 개의 회원번호가 있는데, 이것은 두 회원이 서로 친구임을 나타낸다. " 라는 문장을 통해 무방향 그래프 문제라고 생각했다.

 

문제에서 원하는 건 점수가 가장 낮은 회원들의 점수를 출력하고, 회원을 오름차순으로 정렬해서 출력하는 것!

 

그래서 그냥 for 문으로 1~n 까지 돌도록 했다. 각 for 문에서는 BFS 를 돌려서 curMax 값을 구하고, 마지막에 이 curMax 값이 totalMin 값 보다 작으면 totalMin 값을 curMax 값으로 바꾸도록 했다. (이전에 있었떤 answer 들은 clear 로 다 삭제시켜버림)

 

마지막에는 그냥 answer 벡터 오름차순으로 정렬해서 출력해주면 된다.