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

https://www.acmicpc.net/problem/6118

코드

#include <iostream>
#include <vector>
#include <queue>
using namespace std;

#define MAX 20001
int n, m, maxAns;
int dst[MAX];
vector<int> v[MAX];	
bool visit[MAX];

void bfs() {
	queue<int> q;
	q.push(1);

	visit[1] = true;
	dst[1] = 0;

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

		for (int i = 0; i < v[now].size(); i++) {
			int next = v[now][i];

			if (!visit[next]) {
				visit[next] = true;
				dst[next] = dst[now] + 1;
				q.push(next);
			}
		}
	}

	for (int i = 1; i <= n; i++)
		maxAns = max(maxAns, dst[i]);

	int cnt = 0;
	bool print = false;
	for (int i = 1; i <= n; i++) {
		if (maxAns == dst[i]) {
			cnt++;
			if (!print) {
				cout << i << " ";
				print = true;
			}
		}
	}
	cout << maxAns << " " << cnt;
}

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

	bfs();
	return 0; 
}

설명

bfs를 이용해서 1번 헛간에서 각 헛간까지의 거리를 구합니다.  bfs 이후 먼저 가장 거리가 먼 헛간의 거리를 구한 후 반복문을 돌면서 헛간 번호, 최대 거리를 가진 헛간의 개수를 구하면 됩니다.

느낀 점

bfs에 조건을 추가한 문제입니다.