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

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

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

---

 

Java 코드

 

---

import java.util.Scanner;

public class Main {
  public static void main(String[] args) {
    Scanner sc = new Scanner(System.in);

    int num = 0;
    int min = 1000000000;
    int max = 1000000000;
    int n = sc.nextInt();
    int m = sc.nextInt();
    int arr[][] = new int[n + 1][n + 1];

    for(int i = 1; i <= n; i++) {
      for(int j = 1; j <= n; j++) {
        if(i == j) arr[i][j] = 0;
        else arr[i][j] = max;
      }
    }

    for(int i = 0; i < m; i++) {
      int a = sc.nextInt();
      int b = sc.nextInt();
      arr[a][b] = 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++) {
          if(arr[i][j] > arr[i][k] + arr[k][j]) arr[i][j] = arr[i][k] + arr[k][j];
        }
      }
    }

    for(int i = 1; i <= n; i++) {
      int count = 0;
      for(int j = 1; j <= n; j++) count += arr[i][j];
      if(min > count) {
        min = count;
        num = i;
      }
    }

   System.out.println(num);
  }
}