득이공간
[백준 C++] 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. 조건자 함수 작성 후 해당 함수 포인트를 사용해서 배열의 최소값 출력
'PS > 알고리즘 문제풀이' 카테고리의 다른 글
[백준 C++] 6064 카잉 달력 - 정수론 (1) | 2024.02.16 |
---|---|
[백준 C++] 5525 IOIOI - 문자열 (1) | 2024.02.16 |
[백준 C++] 21736 헌내기는 친구가 필요해 - 너비우선탐색 (0) | 2024.02.16 |
[백준 C++] 11279 최대 힙 - 우선순위큐 (0) | 2024.02.15 |
[백준 C++] 17626 Four Squares - 다이나믹프로그래밍 (0) | 2024.02.15 |