[백준 6118] 숨바꼭질

www.acmicpc.net/problem/6118

6118번: 숨바꼭질

레벨별 순회 후 리프노드 중 가장 적은 번호의 노드를 리턴한다.

bfs를 사용. 

#include <stdio.h>
#include <vector>
#include <queue>
#include <algorithm>

using namespace std;
int n, m;

vector<int> v[20001];
int visited[20001];
queue<int> q;
int main(void)
{
  scanf("%d%d", &n, &m);

  for (int i = 0; i < m; i++)
  {
    int a, b;
    scanf("%d%d", &a, &b);
    v[a].push_back(b);
    v[b].push_back(a);
  }

  q.push(1);
  visited[1] = 1;
  vector<int> ans;
  while (!q.empty())
  {
    int cur = q.front();
    q.pop();

    for (auto a : v[cur])
    {
      if (visited[a] == 0)
      {
        q.push(a);
        visited[a] = visited[cur] + 1;
      }
    }
  }
  int max = 0, cnt = 0, res = 0;
  for (int i = 2; i <= n; i++)
  {
    if (visited[i] > max)
    {
      res = i;
      max = visited[i];
      cnt = 1;
    }
    else if (visited[i] == max)
    {
      cnt++;
    }
  }

  printf("%d %d %d\n", res, visited[res] - 1, cnt);
  return 0;
}