백준 6118번 숨바꼭질 C++

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

 

bfs탐색을 이용하여 해결할 수 있는 문제이다.

2차원 벡터로 그래프를 나타내고 노드와 거리를 저장하도록 pair<int, int> 를 이용하고 found벡터와 함께 bfs탐색을 하면서 문제를 해결하였다.

탐색을 하다가 거리가 갱신되면 답을 갱신하고 cnt를 0으로 초기화 해주고, 만약 거리가 같다면 기존 답과 비교해서 새로 찾은 헛간의 번호가 더 작다면 갱신해주고, cnt를 1 늘려주었다.

 

 

#include <iostream>
#include <string>
#include <vector>
#include <math.h>
#include <algorithm>
#include <utility>
#include <stack>
#include <queue>
#include <math.h>
#include <set>
#include <map>
#include <unordered_map>
#include <unordered_set>

using namespace std;
typedef long long ll;

int n, m;

int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);

	cin >> n >> m;
	int node1, node2;
	vector<vector<int>> graph(n + 1, vector<int>());
	vector<bool> found(n + 1, false);
	for (int i = 0; i < m; i++) {
		cin >> node1 >> node2;
		graph[node1].push_back(node2);
		graph[node2].push_back(node1);
	}
	queue<pair<int, int>> q;
	q.push({ 1,0 });
	found[1] = true;
	int ans = 1;
	int dist = 0;
	int cnt = 0;
	while (!q.empty()) {
		auto a = q.front();
		q.pop();
		if (a.second > dist) {
			cnt = 0;
			dist = a.second;
			ans = a.first;
		}
		if (a.second == dist) {
			cnt++;
			ans = min(ans, a.first);
		}
		for (int next : graph[a.first]) {
			if (found[next]) continue;
			found[next] = true;
			q.push({ next,a.second + 1 });
		}
	}
	cout << ans << " " << dist << " " << cnt;
};