[백준] 알고리즘 1389번 - 케빈 베이컨의 6단계 법칙

케빈 베이컨의 6단계 법칙 문제

소스코드

#include <bits/stdc++.h>
using namespace std;
vector<int> v1[101];
int check[101];
int ans[101];
queue<int> qu;
int n;
int bfs(int x) {
	qu.push(x);
	int cnt = 0;
	while (!qu.empty()) {
		int z = qu.front();
		int size = v1[z].size();
		qu.pop();
		for (int i = 0; i < size; i++) {
			if (check[v1[z][i]] == 0) {
				qu.push(v1[z][i]);
				check[v1[z][i]]=check[z]+1;
			}
		}
	}
	for (int i = 1; i <= n; i++) {
		if (i == x) continue;
		cnt += check[i]-1;
	}
	
	return cnt;
}
int main(){
   ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
   int m;
   cin >> n >> m;
   for (int i= 0; i < m; i++) {
	   int x, y;
	   cin >> x >> y;
	   v1[x].push_back(y);
	   v1[y].push_back(x);
   }
   for (int i = 1; i <= n; i++) {
	   check[i] = 1;
	   ans[i]=bfs(i);
	   for (int j = 1; j <= n; j++) check[j] = 0;
   }
   int idx=1, Min=ans[1];
   for (int i = 1; i <=n; i++) {
	   if (Min > ans[i]) {
		   Min = ans[i];
		   idx = i;
	   }
   }
   cout << idx;
}

문제풀이

BFS를 이용하여 문제를 해결해야한다.

우선 문제는 길지만 결국엔 BFS를 이용해 START지점에서 각 정점까지의 가중치를 구하는 문제이다.