[백준] 1389. 케빈 베이컨의 6단계 법칙 (C++)

문제

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

---

풀이

[플로이드 와샬 알고리즘]

https://yun000.tistory.com/155

플로이드 와샬 알고리즘(Floyd Warshall)

 

예시)

입력

5 5
1 3
1 4
4 5
4 3
3 2

 

1. CHECK - Floyd Warshall Algorithm

플로이드 와샬 알고리즘을 사용하여 왼쪽 그래프가 오른쪽 그래프로 변경된다.

2. CHECK - min

모든 경로에서 모든 경로까지의 최단 거리를 구했으니 이제 각각을 더해가며

최소인 값을 출력하면된다.

---

코드

#include <iostream>
#include <vector>
#define INF 2147483647
using namespace std;

int main() {
	//INPUT
	int N, M;
	cin >> N >> M;
	vector<vector<int>>graph(N+1,vector<int>(N+1,INF));
	for (int i = 1; i <= N; i++) {
		graph[i][i] = 0; // 자기 자신은 0
	}
	int p1, p2;
	for (int i = 0; i < M; i++) {
		cin >> p1 >> p2;
		graph[p1][p2] = 1;
		graph[p2][p1] = 1;
	}

	//CHECK - Floyd Warshall Algorithm
	for (int k = 1; k <= N; k++) {
		for (int i = 1; i <= N; i++) {
			for (int j = 1; j <= N; j++) {
				if (graph[i][k] == INF || graph[k][j] == INF) continue;
				graph[i][j] = min(graph[i][j], graph[i][k] + graph[k][j]);
			}
		}
	}

	//CHECK - min
	int min = INF;
	int result = 0;
	for (int i = 1; i <= N; i++) {
		int sum = 0;
		for (int k = 1; k <= N; k++) {
			sum += graph[i][k];
		}
		if (sum < min) { min = sum; result = i; }
	}

	//RESULT
	cout << result;
}