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

이번 문제도 플로이드-와샬 알고리즘을 이용해서 푸는 문제입니다. 처음 플로이드-와샬 알고리즘에 대해 공부해봐서 적응을 하기 위해서 이어서 풀어보고 있습니다.

 

문제 링크 및 분석

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

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

위에서 이야기했듯이 플로이드-와샬 알고리즘을 이용해야 합니다. 플로이드-와샬을 통해 배열을 만들어준 뒤, 행별로 숫자들을 다 더하여 최솟값을 구하면 됩니다. 아래에서 코드를 보면 더 쉽게 이해가 될 것입니다. 추가로 화면 하단에 플로이드-와샬 알고리즘과 관련된 문제 2가지가 더 있으니 참고하시기 바랍니다.

 

문제 소스 코드

#include <cstdio>
using namespace std;

const int INF = 987654321;
int n, m;
int friends[102][102];
int countfriends[102][102];
void floyd() { // 플로이드 와샬 알고리즘 
	// k : 거쳐가지는 지점
	for (int k = 1; k <= n; k++) {
    	// i : 시작 지점
		for (int i = 1; i <= n; i++) {
        	// j : 도착 지점
			for (int j = 1; j <= n; j++) {
				if (i == j || j == k || i == k) continue;

				if (friends[i][j] > friends[i][k] + friends[k][j]) {
					friends[i][j] = friends[i][k] + friends[k][j];
				}
			}
		}
	}
}
int main(void) {
	int mincnt = 987654321, number, cnt = 0;;
	scanf("%d%d", &n, &m);
	for (int i = 0; i < m; i++) {
		int a, b;
		scanf("%d%d", &a, &b);
		friends[a][b] = 1;
		friends[b][a] = 1;
	}
	
    // i == j 도 아니면서 값이 들어가 있지 않는 부분 INF로
	for (int i = 1; i <= n; i++) {
		for (int j = 1; j <= n; j++) {
			if (i != j && friends[i][j] == 0) {
				friends[i][j] = INF;
			}
		}
	}

	floyd(); // 플로이드-와샬 코드를 거친 배열이 만들어짐

	
	for (int i = 1; i <= n; i++) {
		cnt = 0;
		for (int j = 1; j <= n; j++) {
			cnt += friends[i][j]; // 행별로 다 더함
		}
		if (mincnt > cnt) { // 행들 중 가장 작은 값을 갖는 행 구함
			number = i;
			mincnt = cnt;
		}
	}

	printf("%d\n", number);
}

 

참고하면 좋은 글

[백준 / 11404번] 플로이드

[BOJ] 백준 11404번 플로이드

[백준 / 11403번] 경로 찾기

[BOJ] 백준 11403번 경로 찾기

개발 환경 : Visual Studio 2019