[C++] 백준 1389번 케빈 베이컨의 6단계 법칙 - 플로이드-워셜(Floyd -warshall) 알고리즘

🔍 문제 요약

• 문제 링크: 백준 1389번
• 주요 태그: 그래프, 플로이드-워셜, 최단거리, 전이행렬

문제 설명:
BOJ 유저들 간의 친구 관계가 주어졌을 때,
각 사람을 시작점으로 하여 다른 모든 사람과의 최단 거리의 합을 계산하고,
그 합이 가장 작은 사람의 번호를 출력하는 문제

---

💡 문제 분석

모든 정점에서 다른 모든 정점까지의 최단 거리 합 중 최소를 구하는 문제로,
플로이드–워셜 알고리즘을 사용했다.

• 간선의 가중치는 항상 1 -> 간단하게 거리 계산 가능
• 인접 행렬 기반의 구현
• 경로의 최솟값을 구하기 위해, INT_MAX로 초기화 -> 오버플로우 발생 주의

---

🔑 아이디어

• 플로이드-워셜 알고리즘을 통해
  dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j]) 로
  모든 정점 쌍 간의 최단 경로를 구하기.
• 이후 i번째 유저에 대해 sum(dist[i][j])을 구하고
  이 합이 가장 작은 사람의 번호를 출력
• 다만 dist[i][j]가 초기값 INT_MAX인 상태에서 + 연산이 되면 오버플로우가 발생할 수 있기때문에, 자료형 long long 사용

---

🧩 풀이 전략

1. 인접 행렬 초기화
   • 자기 자신은 0, 나머지는 INT_MAX로 설정
2. 친구 관계 입력받기
   • dist[x][y] = 1, dist[y][x] = 1
3. 플로이드-워셜 알고리즘 수행
4. 케빈 베이컨 수 계산
   • 각 사람마다 dist[i][j]의 합을 구하고, 그 합이 가장 작은 사람을 선택

---

📦 예제 입력 & 출력

• 입력

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

• 출력

3

---

🖥️ 코드

#include <iostream>
#include <climits>
#include <algorithm>

using namespace std;
long long dist[101][101];
long long kevin[101];

int main(void) {
	ios::sync_with_stdio(0);
	cin.tie(0);

	int n, m;
	cin >> n >> m;

	// 거리 초기화
	for (int i = 1; i <= n; i++) {
		for (int j = 1; j <= n; j++) {
			if (i != j)
				dist[i][j] = INT_MAX;
		}
	}

	// 친구 관계 입력
	for (int i = 0; i < m; i++) {
		int x, y;
		cin >> x >> y;
		dist[x][y] = 1;
		dist[y][x] = 1;
	}

	// 플로이드-워셜
	for(int k = 1; k <= n; k++) {
		for (int i = 1; i <= n; i++) {
			for (int j = 1; j <= n; j++) {
				if (dist[i][k] != INT_MAX && dist[k][j] != INT_MAX)
					dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j]);
			}
		}
	}

	// 케빈 수 계산
	long long minKevin = INT_MAX;
	int answer = 0;
	for (int i = 1; i <= n; i++) {
		for(int j = 1; j <= n; j++) {
			kevin[i] += dist[i][j];
		}
		if (minKevin > kevin[i]) {
			minKevin = kevin[i];
			answer = i;
		}
	}
	cout << answer;
	return 0;
}

---

✅ 검증 및 테스트

유저 번호 케빈 베이컨 수(거리 총합)

유저 번호	케빈 베이컨 수 (거리 총합)
1	6
2	8
3	5 ✅
4	5
5	8

→ 문제 조건에 따라, 가장 번호가 작은 3번이 정답

---

⏱️ 시간복잡도

• 전체 시간 복잡도: O(N³)
• N ≤ 100 이므로 충분히 통과 가능
• 배열은 long long 또는 int로도 충분 (단, 오버플로우만 주의)

---

✨ 결론

• 이 문제는 플로이드-워셜의 전형적인 응용 문제
• "모든 정점 간 최단 거리"라는 조건이 보이면  플로이드-워셜 떠올리기!
• 입력 조건이 작고, 가중치가 1이라 하더라도 전체 연결 정보가 필요한 경우에는 플로이드-워셜로 풀면 된다.

 

관련글:

2025.05.11 - [Algorithm] - [Algorithm] 플로이드–워셜 알고리즘(Floyd-Warshall) 완벽 정리 - 그래프 모든 경로 탐색