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

플로이드 와샬 알고리즘으로 문제를 풀었습니다.

친구 관계가 주어졌을 때 친구를 거쳐서 아는 사람을 찾을 수 있습니다.
이 때 다른 모든 사람들과의 관계에서 가장 적게 거쳐서 알 수 있는 사람을 찾는 문제입니다.

map[x][y]에서 x는 출발 위치, y는 도착 위치입니다.
x부터 y까지 갈때 거쳐야 하는 친구의 수가 들어가게 됩니다.

map[x][y] == 0이라면 아직 거쳐야하는 수가 입력되지 않은 상태입니다.
입력되어 있다면 다른 곳을 거쳐서 오는 수와 이미 입력된 수를 비교해서 작은 값을 넣습니다.

이와 같은 방식으로 모든 방향에 대한 수를 전부 구하여서 풀었습니다.

 

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

int people;
int relation;
int map[110][110];

int main(int argc, char *argv[])
{
	memset(map, 0, sizeof(map));

	int a, b;
	int sum = 0;
	int index = 0;
	int minPeople = 987654321;

	cin >> people;
	cin >> relation;

	for (int i = 0; i < relation; ++i) {
		cin >> a;
		cin >> b;

		map[a][b] = map[b][a] = 1;
	}

	for (int k = 1; k <= people; k++) {
		for (int i = 1; i <= people; i++) {
			for (int j = 1; j <= people; j++) {
				if (i == j) {
					continue;
				}
				else if (map[i][k] != 0 && map[k][j] != 0) {
					if (map[i][j] == 0) {
						map[i][j] = map[i][k] + map[k][j];
					}
					else {
						map[i][j] = min(map[i][j], map[i][k] + map[k][j]);
					}
				}
			}
		}
	}

	for (int i = 1; i <= people; ++i) {
		for (int j = 1; j <= people; ++j) {
			sum += map[i][j];
		}
		if (sum < minPeople) {
			minPeople = sum;
			index = i;
		}
		sum = 0;
	}

	cout << index << endl;

	return 0;
}