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

발냄새라는 단어를 듣고 기계공학과를 떠올린 나......

 

최단경로를 찾는 문제이다. 

주어진 간선의 weight 정보가 없고, 단순히 출발점으로부터 얼마나 떨어져있는지 물어보는 문제이기 때문에

충분히 BFS으로 풀 수 있다고 판단을 했다.

 

조심해야 할 점은 그래프가 무향그래프라는 점이다.

그렇기 때문에 입력을 받고, 그래프에 넣을 때 양쪽의 정보를 넣어주어야 문제를 편하게 풀 수 있다.

이런 결의 문제의 경우 인접행렬로 처음에 배열을 int adj[20010][20010]이라고 정의를 하게되면 배열의 사이즈가

4 * 20010 * 20010으로 초기에 너무 커질 것 같아 인접리스트로 푸는것이 더 나은것 같다고 판단했다.

 

#include <bits/stdc++.h>
#define endl '\n'
#define INF 987654321
using namespace std;

int n, m;
vector<int> adj[20010];

int main() {

	ios::sync_with_stdio(false);
	cin.tie(0); cout.tie(0);

	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);
	}
	queue<int> q;
	vector<int> dist(n + 1, INF);

	q.push(1);
	dist[1] = 0;
	while (!q.empty()) {
		int u = q.front(); q.pop();
		for (int v : adj[u]) {
			if (dist[v] > dist[u] + 1) {
				dist[v] = dist[u] + 1;
				q.push(v);
			}
		}
	}

	int way = 0;
	for (int i = 1; i < n + 1; i++) {
		if (dist[i] != INF) way = max(way, dist[i]);
	}
	vector<int> ans;
	for (int i = 1; i < n + 1; i++) {
		if (dist[i] == way) ans.push_back(i);
	}
	sort(ans.begin(), ans.end());

	cout <<  ans[0] << " " << way <<  " " << ans.size() << endl;

	return 0;

}