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

[문제 링크]

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

---

정점들을 연결하는 간선의 가중치가 1인 그래프를 만든 다음, 모든 정점 간의 최단거리를 구하는 플로이드-와샬 알고리즘을 수행하고 모든 정점들의 케빈 베이컨 수를 계산하여 그 값이 가장 작은 인덱스를 출력하도록 구현하였다.

---

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

const int INF = 987654321;
int N, M;
vector<vector<int>> adj(101, vector<int>(101, INF));

void floyd() {
	for (int i = 1; i <= N; i++)
		adj[i][i] = 0;

	for (int k = 1; k <= N; k++)
		for (int i = 1; i <= N; i++)
			for (int j = 1; j <= N; j++)
				adj[i][j] = min(adj[i][j], adj[i][k] + adj[k][j]);
}

int main(void) {
	cin >> N >> M;

	for (int i = 0; i < M; i++) {
		int A, B;
		cin >> A >> B;

		adj[A][B] = 1;
		adj[B][A] = 1;
	}

	floyd();

	int temp = INF;
	int idx;
	for (int i = 1; i <= N; i++) {
		int kebin = 0;
		for (int j = 1; j <= N; j++)
			kebin += adj[i][j];

		if (temp > kebin) {
			temp = kebin;
			idx = i;
		}
	}

	cout << idx << endl;

	return 0;
}

알고리즘 200일 프로젝트 - 164 day