[백준 / BOJ] C++ 1389 케빈 베이컨의 6단계 법칙

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

 

문제

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

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

 

 

풀이

플로이드-워셜 알고리즘을 사용해 각 사람이 다른 사람에 이르기까지의 단계를 각각 구해 케빈 베이컨의 수를 구하고, 최솟값을 가지는 사람의 번호를 출력하는 문제다.

 

 

코드

#include <bits/stdc++.h>
using namespace std;
#define INF 1e9

int main() {
  ios::sync_with_stdio(false);
  cin.tie(NULL);
  int N, M, dist[101][101], m = 1e9, ans = 1;
  cin >> N >> M;
  // dist 배열 초기화
  for (int i = 1; i <= N; i++)
    for (int j = 1; j <= N; j++)
      dist[i][j] = i == j ? 0 : INF;
  // 간선 입력
  while (M--) {
    int a, b;
    cin >> a >> b;
    dist[a][b] = 1;
    dist[b][a] = 1;
  }
  // 플로이드 워셜
  for (int k = 1; k <= N; k++)
    for (int i = 1; i <= N; i++)
      for (int j = 1; j <= N; j++)
        dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j]);
  // 케빈 베이컨 수
  for (int i = 1; i <= N; i++) {
    int sum = 0;
    for (int j = 1; j <= N; j++)
      sum += dist[i][j];
    if (m > sum) {
      m = sum;
      ans = i;
    }
  }
  cout << ans << '\n';
  return 0;
}