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

문제

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

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

 

접근 방법

모든 사람들이 연결되어 있는 상황을 그래프로 표현해 보았다.

이때 두 사람 간의 이어지는 단계는 그래프에서의 두 정점의 최단 거리라고 볼 수 있다.

케빈 베이컨 게임은 모든 사람들 간의 최단 거리가 필요하므로

이때 적용할 수 있는 알고리즘은 플로이드 와샬 알고리즘이다.

 

코드

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

int n, m, a, b, ans, minKevin = 9999999, sum;
int earth[101][101];

void floyd() {
	for (int k = 1; k <= n; k++) {
		for (int i = 1; i <= n; i++) {
			for (int j = 1; j <= n; j++) {
				if (earth[i][j] > earth[i][k] + earth[k][j]) {
					earth[i][j] = earth[i][k] + earth[k][j];
				}
			}
		}
	}
}

int main() {
	cin >> n >> m;
	fill(&earth[0][0], &earth[100][101], 9999999);
	for (int i = 1; i <= n; i++) {
		earth[i][i] = 0;
	}

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

	floyd();
	
	for (int i = 1; i <= n; i++) {
		sum = 0;
		for (int j = 1; j <= n; j++) {
			sum += earth[i][j];
		}
		if (sum < minKevin) {
			ans = i;
			minKevin = sum;
		}
	}
	cout << ans << '\n';
}

모든 정점 간의 거리를 저장할 이차원 배열을 선언하고

갈 수 없는 곳은 무한대, 자기 자신은 0, 입력된 친구 관계는 1로 초기화해 주었다.

플루이드 와샬 알고리즘을 3중 for문으로 구현하여 모든 정점 간의 최단거리를 구하였다.

나온 결과를 통해 모든 케빈 베이컨 수를 구하여 번호가 가장 작은 사람을 출력하였다.