[백준] 6118번 숨바꼭질

문제: 6118번: 숨바꼭질

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>> graph;
vector<bool> visits;

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

    int n, m;
    cin >> n >> m;
    graph = vector<vector<int>>(n + 1); // 0번 인덱스 안 써
    visits = vector<bool>(n + 1);

    for (int i = 0; i < m; i++) {
        int a, b;
        cin >> a >> b;

        graph[a].push_back(b);
        graph[b].push_back(a);
    }
    int curMax = 0;
    queue<pair<int, int>> nexts;
    nexts.push({ 1, 0 });
    visits[1] = true;

    vector<int> answers;
    while (!nexts.empty()) {
        pair<int, int> cur = nexts.front(); nexts.pop();
        if (curMax <= cur.second) {
            if (curMax < cur.second) {
                answers.clear();
            }
            answers.push_back(cur.first);
            curMax = cur.second;
        }

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

            nexts.push({ next, cur.second + 1 });
            visits[next] = true;
        }
    }
    sort(answers.begin(), answers.end());
    cout << answers[0] << " " << curMax << " " << answers.size();

    return 0;
}