[백준] 1389 케빈 베이컨의 6단계 법칙 (java)

1. 링크

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

 

2. 풀이

키워드: 플로이드 와샬

24. 플로이드 와샬(Floyd Warshall) 알고리즘

 

- 플로이드 와샬 알고리즘을 이용한다.

- 모든 정점 사이의 최단 거리를 구한다.

- 구한 최단 거리를 합하고 그 합이 가장 작은 인덱스를 정답으로 출력한다.

풀이 순서

1. NxN 의 2차원 배열을 생성한다.

2. 2차원 배열의 모든 값을 INF 로 초기화한다.

   - 최단 거리를 구해야하기 때문에 기준이 되는 값을 최대값 (MAX) 로 세팅한다.

INF = 987654321;

3. i=j 인 값은 (열,행이 같은 인덱스) 0으로 초기화한다.

   - 최단거리를 구하지 않아도 당연히 0이기 때문에 0으로 초기화한다.

4. 입력으로 주어진 간선은 양방향으로 1로 세팅한다.

5. 반복문 3개를 통해 최단경로가 거치는 경로보다 크다면 거치는 경로의 값으로 업데이트 한다.

// 최단경로 초기화
if (arr[i][j] > arr[i][k] + arr[k][j]) { // 최단경로가 거치는 경로보다 더 크다면
	arr[i][j] = arr[i][k] + arr[k][j]; // 최단경로를 거치는 경로로 업데이트
}

 

6. 배열의 모두 업데이트 되었다면 각 인덱스 별로 최단거리의 합을 구한다.

7. 최단거리의 합이 가장 작은 인덱스를 결과로 출력한다.

3. 소스코드

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.StringTokenizer;

public class BG_케빈베이컨의6단계법칙 {

  static final int INF = 987654321;

  public static void main(String[] args) throws IOException {
    BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

    StringTokenizer st;

    String[] s = br.readLine().split(" ");
    int N = Integer.parseInt(s[0]);
    int M = Integer.parseInt(s[1]);

    int[][] arr = new int[N][N];
    for (int i = 0; i < N; i++) {
      for (int j = 0; j < N; j++) {
        if (i == j) {
          arr[i][j] = 0;
          continue;

        }
        arr[i][j] = INF;
      }
    }

    for (int i = 0; i < M; i++) {
      String[] s1 = br.readLine().split(" ");
      int x = Integer.parseInt(s1[0]);
      int y = Integer.parseInt(s1[1]);

      arr[x - 1][y - 1] = 1;
      arr[y - 1][x - 1] = 1;
    }

    for (int k = 0; k < N; k++) { // 대상 사람
      for (int i = 0; i < N; i++) {
        for (int j = 0; j < N; j++) {
          // 최단경로 초기화
          if (arr[i][j] > arr[i][k] + arr[k][j]) { // 최단경로가 거치는 경로보다 더 크다면
            arr[i][j] = arr[i][k] + arr[k][j]; // 최단경로를 거치는 경로로 업데이트
          }
        }
      }
    }

    int res = INF;
    int index = -1;

    for (int i = 0; i < N; i++) {
      int sum = 0;
      for (int j = 0; j < N; j++) {
        sum += arr[i][j]; // 왜 다 합치는거지? 아 각각의 가는길 모두 합쳐서!
      }

      if (res > sum) {
        res = sum;
        index = i; // 케빈 베이컨의 수가 가장 작은 사람
      }
    }

    bw.write(index+1 + "\n");
    bw.flush();
    br.close();
    bw.close();
  }

}