백준 1389번 케빈 베이컨의 6단계 법칙

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

 

bfs로 그래프를 탐색하는 방식으로 문제를 해결하였다.

 

#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>
#include <iomanip>

using namespace std;
using ll = long long;

void RefreshFound(vector<bool>& found, int n) {
	for (int i = 1; i <= n; i++) {
		found[i] = false;
	}
}

int bfs(int n, const vector<vector<int>>& graph, vector<bool> &found) {
	int ret = 0;
	found[n] = true;
	queue<pair<int, int>> q;
	q.push({ n,0 });
	while (!q.empty()) {
		auto curr = q.front();
		q.pop();
		ret += curr.second;
		for (auto next : graph[curr.first]) {
			if (found[next]) continue;
			found[next] = true;
			q.push({ next,curr.second + 1 });
		}
	}
	return ret;
}

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

	int n, m;
	cin >> n >> m;
	vector<vector<int>> graph(n + 1, vector<int>());
	vector<bool> found(n + 1, false);
	for (int i = 0; i < m; i++) {
		int a, b;
		cin >> a >> b;
		graph[a].push_back(b);
		graph[b].push_back(a);
	}
	int minScore = 987654321;
	int ans = 0;
	for (int i = 1; i <= n; i++) {
		RefreshFound(found, n);
		int score = bfs(i, graph, found);
		if (score < minScore) {
			minScore = score;
			ans = i;
		}
	}
	cout << ans;
};