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

 

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

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

플루이드 와샬을 이용하면 쉽게 풀리는 문제이다.

x와 y가 친구 사이일 때 모든 사람들이 친구가 되는데 비용을 갱신한다.

그리고 최소비용을 가진 사람을 구하는 문제이다.

한가지 플루이드 와샬과 다른 점은 왕복이 가능한 노드라는 점이다.

#include <iostream>
#define INF 100000 //무한대를 100000으로 설정
using namespace std;

int mat[101][101]; //사람수가 100명이니까 100 * 100으로 구현
int d[101][101]; //최단 경로를 저장할 변수
long long int shortdistance[101]; //각 노드에서 다른 노드로 이동할 수 있는지를 담아놓을 변수

void floydwarshall() {
	int check = 100000000;
	int ans; //답
	int a, b; //a는 사람 수, b는 반복횟수


	cin >> a >> b;
	for (int i = 0; i < b; i++) {
		int x, y; //x는 현재 자기 자신, y는 친구
		cin >> x >> y;
		mat[x][y] = 1; //현재 x가 y와 친구임을 표현
		mat[y][x] = 1; //현재 y가 x와 친구임을 표현
	}

	for (int i = 1; i <= a; i++) {
		for (int j = 1; j <= a; j++) {
			if (mat[i][j] == 0 && i != j) { //현재 도달할 수 없고 자기자신이 아닌 노드는
				mat[i][j] = INF; //무한대로 초기화
			}
			d[i][j] = mat[i][j]; //최단비용을 현재 비용으로 갱신
		}
	}


	//모든 경로에 대해 dp형식으로 비교
	for (int k = 1; k <= a; k++) { //거쳐가는 지점
		for (int i = 1; i <= a; i++) { //출발지점
			for (int j = 1; j <= a; j++) { //도착지점
				if (d[i][k] + d[k][j] < d[i][j]) { //현재 i -> j로 가는 방법 중 현재로써 가장 짧은 방법과 k를 거쳐 가는 방법 두 개를 비교
					d[i][j] = d[i][k] + d[k][j]; //거쳐가는 것이 짧으면 거쳐가는 것으로 초기화
				}
			}
		}
	}


	//각 노드에 대한 이동 비용을 더한다.
	for (int i = 1; i <= a; i++) {
		for (int j = 1; j <= a; j++) {
			shortdistance[i] = shortdistance[i] + d[i][j];
		}
	}


	//가장 비용이 안드는 노드를 찾는다. 앞에서뷰터 찾아서 비용이 같더라도 최소 노드가 자동으로 구분이 된다.
	for (int i = 1; i <= a; i++) {
		if (check > shortdistance[i]) { //현재 최단비용보다 i번째 노드의 최단비용이 작으면
			ans = i; //답 갱신
			check = shortdistance[i]; //최단비용 갱신
		}
	}


	cout << ans;
}


int main() {
	floydwarshall();
}