백준 1389번 [케빈 베이컨의 6단계 법칙](C++) -yes6686- 티스토리

백준 문제 풀이: 1389 [케빈 베이컨의 6단계 법칙]

---

문제 링크: https://www.acmicpc.net/problem/1389

문제 설명:

그래프에서 각 노드 간의 최단 거리를 구하고, 특정 노드에서 다른 모든 노드까지의 거리를 합산한 값(케빈 베이컨 수)이 가장 작은 노드를 출력하는 프로그램을 작성하세요.

입력 조건:

• 첫째 줄에 사용자 수 n과 친구 관계 수 m이 주어집니다. (2 ≤ n ≤ 100, 1 ≤ m ≤ 5000)
• 둘째 줄부터 m개의 줄에 친구 관계가 주어집니다. 각 줄에는 두 정수 a와 b가 주어지며, 이는 a와 b가 친구임을 의미합니다.

출력 조건:

• 케빈 베이컨 수가 가장 작은 사용자 번호를 출력합니다. 답이 여러 개라면 번호가 가장 작은 사용자를 출력합니다.

---

문제 해결 코드

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

int arr[101][101];

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

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

    // 친구 관계 입력
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= n; j++) {
            if (i != j) {
                arr[i][j] = 1e9; // 초기값: 큰 값
            }
        }
    }

    for (int i = 0; i < m; i++) {
        int a, b;
        cin >> a >> b;
        arr[a][b] = 1;
        arr[b][a] = 1;
    }

    // 플로이드-워셜 알고리즘
    for (int k = 1; k <= n; k++) {
        for (int i = 1; i <= n; i++) {
            for (int j = 1; j <= n; j++) {
                arr[i][j] = min(arr[i][j], arr[i][k] + arr[k][j]);
            }
        }
    }

    // 케빈 베이컨 수 계산
    int minValue = 1e9;
    int resultIndex = 0;
    for (int i = 1; i <= n; i++) {
        int sum = 0;
        for (int j = 1; j <= n; j++) {
            if (arr[i][j] != 1e9) {
                sum += arr[i][j];
            }
        }
        if (sum < minValue) {
            minValue = sum;
            resultIndex = i;
        }
    }

    cout << resultIndex << '\n';
    return 0; // 프로그램 정상 종료
}

---

코드 설명

위 코드는 플로이드-워셜 알고리즘을 사용하여 모든 노드 간의 최단 거리를 계산한 뒤, 케빈 베이컨 수가 가장 작은 노드를 찾습니다.

• 그래프 초기화:
  • `arr[i][j]`는 i와 j 간의 거리로, 초기값은 1e9로 설정하여 연결되지 않음을 표시합니다.
• 플로이드-워셜 알고리즘:
  • 중간 노드 k를 경유하여 i에서 j로 가는 최단 거리를 갱신합니다.
  • `arr[i][j] = min(arr[i][j], arr[i][k] + arr[k][j]);`
• 케빈 베이컨 수 계산:
  • 각 노드에 대해 다른 모든 노드와의 거리 합을 계산합니다.
  • 합이 가장 작은 노드의 번호를 결과로 저장합니다.

시간 복잡도 분석:

• 플로이드-워셜 알고리즘: O(n³).
• 케빈 베이컨 수 계산: O(n²).

전체 시간 복잡도는 O(n³)로, n ≤ 100인 경우 충분히 효율적으로 동작합니다.

---

결과

다음은 입력 예시와 출력 결과입니다:

입력:
5 5
1 3
1 4
4 5
4 3
3 2

출력:
3

위 입력에서 3번 사용자가 케빈 베이컨 수가 가장 작습니다.

다른 접근 방식이나 개선 사항이 있다면 댓글로 공유 부탁드립니다!