백준 1389 케빈 베이컨의 6단게 법칙 (c++) : 피너클

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

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

플로이드 와샬을 이용한 문제다.

플로이드 와샬은 그래프의 모든 정점중 두 쌍의 최단거리를 구하는 알고리즘이다.

이번 문제에서는 사람과 사람 사이의 친구가 되는 가장 짧은 단계를 구하는데 사용된다.

cin >> n >> m;

memset(f, 0, sizeof(f));

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

n,m을 입력받고 f를 0으로 초기화한다 f는 사람사이의 관계를 나타내는 배열이다. 0이면 서로 친구가 아닌것이다.

그후 m번만큼 a와 b를 입력받고 f[a][b] 와 f[b][a]를 1로 바꾼다. 서로 친구라는 의미다.

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

그후 플로이드 와샬 알고리즘을 돌려준다. i와 j가 같다면 사람이 같다는 소리니 그냥 넘긴다.

만약 f[i][k]와 f[k][j]가 0이 아니라면 조건문을 돌린다.

f[i][j]가 0이라면 서로 연결되있지 않다는 소리니 바로 f[i][k]와 f[k][j]를 더한 값을 넣어준다.

f[i][j]가 0이 아니라면 f[i][j]와 f[i][k] + f[k][j]중 더 작은 수를 넣는다.

int ans = 0, sum = 987654321;
for (int i = 1; i <= n; i++) {
	int s = 0;
	for (int j = 1; j <= n; j++) {
		s += f[i][j];
	}
	if (s < sum) ans = i, sum = s;
}
cout << ans << endl;

그후 정답을 구해준다. f[i]가 모든 사람과 연결되는 값을 s에 넣은뒤 만약 s가 sum보다 낮다면 ans와 sum을 업데이트한다.

그후 ans를 출력하면된다.

#include <iostream>
#include <string.h>
#include <algorithm>

using namespace std;

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

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

	cin >> n >> m;

	memset(f, 0, sizeof(f));

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

	for (int k = 1; k <= n; k++) {
		for (int i = 1; i <= n; i++) {
			for (int j = 1; j <= n; j++) {
				if (i == j) continue;
				if (f[i][k] && f[k][j]) {
					if (f[i][j] == 0) f[i][j] = f[i][k] + f[k][j];
					else f[i][j] = min(f[i][j], f[i][k] + f[k][j]);
				}
			}
		}
	}
	int ans = 0, sum = 987654321;
	for (int i = 1; i <= n; i++) {
		int s = 0;
		for (int j = 1; j <= n; j++) {
			s += f[i][j];
		}
		if (s < sum) ans = i, sum = s;
	}
	cout << ans << endl;
}