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

백준 1389

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

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

풀이 전 나의 생각

친구 관계의 정보가 주어질 때, 케빈 베이컨의 수가 가장 작은 사람을 구해야한다.

케빈 베이컨이란 현재 선택된 사람으로 부터 어떤 친구까지 갈 수 있는 단계의 총합을 말한다.

 

조건

-N (2 ≤ N ≤ 100)

-M (1 ≤ M ≤ 5,000)

 

과정

문제 설명은 정말 길지만 결국, 문제에서 요구하는 건

친구 관계 그래프에서 어떤 시작 노드가 주어졌을 때, 그 노드가 모든 노드를

최소로 탐색한 횟수를 구하는 것이다.

 

최소 횟수를 구하는 것이니 BFS를 사용할 수 있고

어떤 지점을 거쳐서 가는지, 차례대로 가는지 비교하기 때문에

플로이드 - 워셜 알고리즘도 사용할 수 있다.

 

풀이에서는 BFS를 사용했으며 과정은 다음과 같다.

 

1. 친구 관계를 저장한다.

2. 노드의 최소 탐색 횟수를 구하기 위해 BFS 탐색을 진행한다.

3. 케빈 베이컨을 구하기 위해 각 노드의 현재 탐색 횟수를 저장한다. 

4. 케빈 베이컨의 수의 최소값을 찾아내고 답을 구한다. 

풀이

#include <iostream>
#include <algorithm>
#include <vector>
#include <cmath>
#include <string>
#include <queue>
#include <string.h>
#include <limits.h>
#include <cstdio>
#include <map>

using namespace std;

vector<vector<int>>link(101);
bool visited[101];

//최소 탐색 횟수를 구하기 위한 BFS탐색 진행
int bfs(int st)
{
	fill(visited, visited + 101, false);

	visited[st] = true;

	int kevin = 0;
	queue<pair<int, int>> q;

	q.push(make_pair(st, 0));

	while (!q.empty())
	{
		int now = q.front().first;
		int score = q.front().second;
		q.pop();

		kevin += score;

		for (int next : link[now])
		{
			if (!visited[next])
			{
				visited[next] = true;
				q.push(make_pair(next, score + 1));
			}
		}
	}
	return kevin;
}

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

	int N, M, MIN = INT_MAX, ans = 0;
	cin >> N >> M;

	//친구 관계 저장
	for (int i = 0; i < M; i++)
	{
		int u, v;
		cin >> u >> v;

		link[u].push_back(v);
		link[v].push_back(u);
	}

	// 케빈 베이컨의 최소값과 최종값 갱신
	for (int i = 1; i <= N; i++)
	{
		int kevin_bacon = bfs(i);

		if (MIN > kevin_bacon)
		{
			MIN = kevin_bacon;
			ans = i;
		}
	}

	cout << ans;
}