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

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

1. 문제요약

- 케빈 베이컨 6단계 법칙 : 임의의 두 사람이 최소 몇 단계 만에 이어지는가

- 한 사람이 다른 모든 사람과 케빈 베이컨의 합이 최소인 사람을 출력

- 같은 사람이 있다면 번호가 작은 사람을 출력

2. 접근방법

- 한 사람이 다른사람까지 도달하는데 최소 단계

- 한 사람이 다른사람과의 케빈 베이컨을 하고

   n 명의 사람 전부다 해봄

3. 시간복잡도

- 최소 경로 찾기

  플로이드 => N^3

  bfs => VE

4. 회고

- 플로이드는 거리 초기값이 중요함

  최소 단계 합을 찾는 과정이 필요함

- bfs는 방문여부를 알아야 하므로 배열이 하나 더 필요함

  좀 더 깔끔하게 만들 수 있을거 같은데...

- dfs는 깊이 우선 탐색이므로 최단 거리가 나오면 갱신해줘야 함

소스코드 : 플로이드

#include<iostream>
using namespace std;

int n, m, f[101][101];

int main(void){
	cin >> n >> m;

	for (int i = 0; i < n + 1; i++)
		for (int j = 0; j < n + 1; j++)
			if (i == j) f[i][j] = 0;
			else f[i][j] = 987654321;

	int a, b;
	for (int i = 0; i < m; i++){
		cin >> a >> b;
		f[a][b] = f[b][a] = 1;
	}

	for (int k = 1; k < n + 1; k++)
		for (int i = 1; i < n + 1; i++)
			for (int j = 1; j < n + 1; j++){
				if (i == j) continue; // 굳이 필요는 없음
				if (f[i][k] + f[k][j] < f[i][j])
					f[i][j] = f[j][i] = f[i][k] + f[k][j];
			}

	int min = 987654321, ans = 0;
	for (int i = 1; i < n + 1; i++){
		int temp = 0;
		for (int j = 1; j < n + 1; j++){
			temp += f[i][j];
		}
		if (temp < min){
			min = temp;
			ans = i;
		}
	}

	cout << ans << "\n";

	return 0;
}

소스코드 : bfs

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

int n, m, f[101][101], check[101][101];

int main(void){
	cin >> n >> m;
	int a, b;
	for (int i = 0; i < m; i++){
		cin >> a >> b;
		f[a][b] = f[b][a] = 1;
	}

	int min = 987654321, ans = 0;
	queue<int> q;
	for (int i = 1; i < n + 1; i++){
		q.push(i);
		check[i][i] = true;

		int temp = 0;
		while (!q.empty()){
			int now = q.front();
			q.pop();

			for (int j = 1; j < n + 1; j++){
				if (!check[i][j] && f[now][j] == 1){
					q.push(j);
					f[i][j] = f[i][now] + f[now][j];
					check[i][j] = true;
					temp += f[i][j];
				}
			}
		}

		if (temp < min){
			min = temp;
			ans = i;
		}
	}
	cout << ans << "\n";
	return 0;
}

[출처 : BOJ, 문제에 대한 모든 권리는 BOJ(acmicpc.net, startlink)에 있음]