6118번

6118번 - 숨바꼭질

가중치가 없어서 BFS로 풀 수 있는 문제였다.

BFS를 돌린 후, 가장 큰값을 찾고, 갯수를 찾으면 되는 문제.

<정답 코드>

#include<iostream>
#include<queue>
#include<vector>
using namespace std;
int main()
{
    //freopen("input.txt", "r", stdin);
    int n, m;
    cin >> n >> m;
    vector<vector<int>> v(n + 1);
    vector<int> dist(n + 1,-1);
    while (m--)
    {
        int from, to;
        cin >> from >> to;
        v[from].push_back(to);
        v[to].push_back(from);
    }
 
    queue<int> q;
    q.push(1);
    dist[1] = 0;
 
    while (!q.empty())
    {
        int here = q.front();
        q.pop();
 
        for (int i = 0; i < v[here].size(); i++)
        {
            int there = v[here][i];
 
            if (dist[there] == -1)
            {
                dist[there] = dist[here] + 1;
                q.push(there);
            }
        }
    }
 
    int maxx = 0;
    int place, cnt = 0;
    for (int i = 2; i <= n; i++)
    {
        if (dist[i] > maxx)
        {
            place = i;
            maxx= dist[i];
        }
    }
 
    for (int i = 2; i <= n; i++)
    {
        if (dist[i] == maxx)
        {
            cnt++;
        }
    }
 
    cout << place << " " << maxx << " " << cnt << endl;
    return 0;
}