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

문제

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

---

문제 요약

케빈 베이컨의 6단계 법칙에 의하면,

지구에 있는 모든 사람들은 최대 6단계 이내에서 서로 아는 사람으로 연결될 수 있다.

 

케빈 베이컨 수는 모든 사람에 도달할 수 있는 단계 수의 합을 의미한다.

 

N명의 유저 간  M개의 친구 관계가 주어졌을 때, 케빈 베이컨 수가 가장 작은 사람의 번호를 출력한다.

---

코드

#include <iostream>
#include <algorithm>
#include <vector>

using namespace std;

int n, m;

// dist[i][j]: i번 -> j번 최단 거리
int dist[110][110];

int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);
	
	cin >> n >> m;

	for (int i = 1; i <= n; i++) {
		for (int j = 1; j <= n; j++) {
			if (i == j) {
				dist[i][j] = 0;
			}
			else {
				dist[i][j] = 1e9;
			}
		}
	}

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

		dist[a][b] = 1;
		dist[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 (dist[i][k] + dist[k][j] < dist[i][j]) {
					dist[i][j] = dist[i][k] + dist[k][j];
				}
			}
		}
	}

	int res;
	int min_dist = 1e9;

	for (int i = 1; i <= n; i++) {
		int sum_dist = 0;

		for (int j = 1; j <= n; j++) {
			sum_dist += dist[i][j];
		}

		if (sum_dist < min_dist) {
			res = i;
			min_dist = sum_dist;
		}

	}

	cout << res;

	return 0;
}

---

코드 설명

친구 관계를 거리 1인 간선으로 연결하여 그래프를 구성하면,

 

각 사람마다 모든 사람까지의 최단거리를 구해야 하므로, 플로이드 워셜 알고리즘을 사용한다.

 

dist[i][j]에는 i번 친구에서 j번 친구까지 도달할 수 있는 최소 단계 수를 저장한다.

 

1. 자신과 자신의 관계를 거리 0으로 설정하고, 나머지 관계를 무한대로 설정한다.

 

2. 직접적인 친구 관계를 거리 1로 설정한다.

 

3. 삼중 반복문을 통해 i번 친구에서 k번 친구를 거쳐 j번 친구로 도달하는 최단 거리를 갱신한다.

 

4. 각 사람마다 모든 사람까지의 최단 거리 합이 가장 작은 사람의 번호를 출력한다.

---

고찰

플로이드 워셜 문제에서 주의할 점은 삼중 반복문의 인덱스 순서이다.

 

k, i, j 순으로 진행해야 올바른 결과가 도출된다.