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

www.acmicpc.net/problem/1389

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

---

 

모든 정점에 대해 bfs를 수행하며 해당 정점으로부터의 거리를 모두 더해준값들을 배열에 저장한뒤, 최소값을 찾아 출력해주면 된다.

 

#include<iostream>
#include <algorithm>
#include<vector>
#include<queue>
using namespace std;

vector<int> v[101];
int n, m;
int dist[101];
bool visited[101];
int result[101];
void bfs(int st) {
	//bfs전 초기화
	for (int i = 0; i <= n; i++) {
		visited[i] = false;
		dist[i] = 0;
	}
	queue<int> q;

	q.push(st);
	visited[st] = true;
	while (!q.empty()) {
		int now = q.front();
		q.pop();
		for (int i = 0; i < v[now].size(); i++) {
			int next = v[now][i];
			if (!visited[next]) {
				visited[next] = true;
				dist[next] = dist[now] + 1;
				q.push(next);
				result[st] += dist[next];
			}
		}
	}

}

int main() {
	cin >> n >> m;
	for (int i = 0; i < m; i++) {
		int from, to;
		cin >> from >> to;
		v[from].push_back(to);
		v[to].push_back(from);
	}
	for (int i = n; i >=1; i--) {
		bfs(i);
		
	}
	int Min = result[n];
	int mini = n;
	for (int i = n - 1; i >= 1; i--) {
		if (Min >= result[i]) {
			mini = i;
			Min = result[i];
		}
	}
	cout << mini;
	return 0;
}