[백준] 1389번 케빈 베이컨의 6단계 법칙 C++ 코드

코드

#include <iostream>
#include <queue>
#include <algorithm>
#include <string>
#include <vector>

using namespace std;

int n, m,a,b, visited[103],res=987654321,resnum;
vector<int> adj[103];
// bfs
int bfs(int x) {
	fill(visited, visited + 103, 0);
	queue<int> q;
	q.push(x);
	visited[x] = 1;
	while (!q.empty()) {
		int pn = q.front();
		q.pop();
		for (int i : adj[pn]) {
			if (!visited[i]) {
				visited[i] = visited[pn] + 1;
				q.push(i);
			}
		}
	}
	int tmp = 0;
	for (int i = 1; i < n + 1; i++) tmp += visited[i] - 1;
	return tmp;
}

int main() {
	cin >> n >> m;
	for (int i = 0; i < m; i++) {
		cin >> a >> b;
		adj[a].push_back(b);
		adj[b].push_back(a);
	}
	for (int i = 1; i < n + 1; i++) {
		int tmpnum = bfs(i);
		if (tmpnum < res) {
			res = tmpnum;
			resnum = i;
		}
	}
	cout << resnum << '\n';
	return 0;
}

풀이

케빈 베이컨 수를 구하는 문제였다. 케빈 베이컨 수가 가장 적은 사람을 구하는 문제라서 해당 사람에게 최단거리로 도달할 수 있어야 한다. 그래서 bfs를 사용했다. bfs로 케빈 베이컨 수를 구하고 이것이 가장 작은 사람을 찾아 출력하면 되는 문제.