[C++] 백준 6118번 숨바꼭질

문제 링크

6118번: 숨바꼭질

문제 요약

그래프가 주어질 때, 1번 정점으로부터 가장 멀리 떨어져 있는 정점들을 구해야 한다.
그리고 다음 항목에 해당하는 값들을 출력하면 된다.
1. 정점 번호가 가장 낮은 정점의 정점 번호
2. 1번 정점으로부터의 거리
3. 가장 멀리 떨어져 있는 정점들의 개수

접근 방법

가중치가 없는 그래프이기 때문에 1번 정점으로부터의 거리는 너비 우선 탐색을 통해서 구할 수 있습니다.

1. 너비 우선 탐색을 통해서 1번 정점으로부터의 거리를 구한 뒤에 dist라는 이름의 배열에 저장해 준다.
2. 반복문을 통해서 거리의 최댓값을 구한다.
3. 다시 반복문을 돌리면서 최댓값이 최초로 나타나는 정점 번호, 최댓값과 거리가 같은 정점의 수를 저장해준다.
4. 구한값들을 출력해준다.

코드

#include <bits/stdc++.h>
#define VPRT(x, type) copy(x.begin(), x.end(), ostream_iterator<type>(cout, " "))
#define ALL(x) x.begin(), x.end()
#define FASTIO ios::sync_with_stdio(false), cin.tie(0), cout.tie(0)
#define endl '\n'
#define MAX 20001

using namespace std;

int n, m, dist[MAX];
bool visited[MAX];
vector<int> adj[MAX];

void bfs(void)
{
	queue<int> q;
	q.push(1);
	dist[1] = 0;
	visited[1] = true;

	while (!q.empty())
	{
		int now = q.front();
		q.pop();

		for (auto& next : adj[now])
		{
			if (!visited[next])
			{
				q.push(next);
				dist[next] = dist[now] + 1;
				visited[next] = true;
			}
		}
	}

	int max_ = 0;
	for (int i = 1; i <= n; i++)
		max_ = max(max_, dist[i]);

	int res = 0, cnt = 0;
	bool flag = false;
	for (int i = 1; i <= n; i++)
	{
		if (max_ == dist[i])
		{
			if (!flag)
				flag = true, res = i;
			cnt++;
		}
	}

	cout << res << ' ' << max_ << ' ' << cnt << endl;
}

int main(void)
{
	FASTIO;
	cin >> n >> m;

	for (int i = 0; i < m; i++)
	{
		int a, b;
		cin >> a >> b;
		adj[a].push_back(b);
		adj[b].push_back(a);
	}

	bfs();
	return 0;
}