[백준 C++] 1389 케빈 베이컨의 6단계 법칙 - 플로이드워셜

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

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

const int Infinite = INT_MAX;

int Distance[101][101];

vector<pair<int, int>> OrderedList;
bool Compare(const pair<int, int>& Left, const pair<int, int>& Right)
{
	return (Left.second == Right.second) ? Left.first < Right.first : Left.second < Right.second;
}

int N, M;
void FloydWarshall()
{
	for (int K = 1; K <= N; ++K)
	{
		for (int S = 1; S <= N; ++S)
		{
			if (Distance[S][K] == Infinite)
			{
				continue;
			}

			for (int E = 1; E <= N; ++E)
			{
				if (Distance[K][E] == Infinite)
				{
					continue;
				}

				Distance[S][E] = min(Distance[S][E], Distance[S][K] + Distance[K][E]);
			}
		}
	}
}

int main()
{
	ios::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)
			{
				Distance[i][j] = Infinite;
			}
		}
	}

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

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

	FloydWarshall();

	for (int i = 1; i <= N; ++i)
	{
		int Count = 0;
		for (int j = 1; j <= N; ++j)
		{
			Count += Distance[i][j];
		}
		OrderedList.emplace_back(i, Count);
	}

	cout << (*min_element(OrderedList.begin(), OrderedList.end(), Compare)).first;
}

---

 

N의 최대 개수가 적고 모든 노드로부터 다른 모든 노드로의 최단경로를 탐색해야 하기 때문에

플로이드 워셜 알고리즘을 사용해서 푸는 문제입니다.

풀이 과정은 다음과 같습니다.

 

1. 최단 거리 행렬 초기화 - 자기 자신(start == end)은 0, 나머지는 무한

2. 최단 거리 행렬에 그래프 데이터 저장

3. 점화식으로 행렬 업데이트 - 3중 for문의 형태: 경유지 노드 K (1~N), 출발 노드 S (1~N), 도착 노드 E (1~N)

- 점화식: D[S][E] = min(D[S][E], D[S][K] + D[K][E])

4. 최단 거리 행렬 정보를 통해 각 노드의 케빈 베이컨의 수를 도출 후 배열에 저장

5. 조건자 함수 작성 후 해당 함수 포인트를 사용해서 배열의 최소값 출력