<백준> 1389번 자바 알고리즘[플로이드 와샬]

import java.util.Scanner;



class Main {

  private static int n;
  private static int m;
  private static int[][] distance;
  private static int INF = 5001;
  public static void main(String[] args) {
    Scanner sc = new Scanner(System.in);
    n = sc.nextInt();
    m = sc.nextInt();
    distance = new int[n][n];

    // 초기화 
    for(int i=0; i < n; i++){
      for(int j=0; j < n; j++){
        if(i == j){
          distance[i][j] = 0;
        }
        else {
          distance[i][j] = INF;
        }
      }
    }
    // 입력
    for(int j=0; j < m; j++){
      int start = sc.nextInt() - 1;
      int end = sc.nextInt() - 1;
      distance[start][end] = 1;
      distance[end][start] = 1;
    }
    floyd();

    //출력
    int[] ans = new int[n];
    int min = Integer.MAX_VALUE;

    for(int i = 0; i < n; i++){
      int sum = 0;

      for(int j = 0; j < n; j++){
        sum += distance[i][j];
      }
      ans[i] = sum;
      // 자주 사용되는 방식 
      if(sum < min){
          min = sum;
      }
    }
    
    for(int i = 0; i < n; i++){
      if(ans[i] == min){
        System.out.println(i + 1);
        return;
      }
    }



  }
  private static void floyd() {
    for(int k = 0; k < n; k++){
      for(int i = 0; i < n; i++){
        for(int j = 0; j < n; j++){
          distance[i][j] = Math.min(distance[i][j], distance[i][k] + distance[k][j]);
        }
      }
    }
  }

}

https://blog.naver.com/ndb796/221234427842

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

플로이드 와샬을 처음 접해서 위의 블로그를 통해 개념을 잡았습니다 

 

 

플로이드 와샬 알고리즘만 이해하면 

정답 구하는건 어렵지 않습니다 

 

min을 Max로 설정하고 

for을 통해서 반복하면서 가장 최솟값을 찾는것은 다른 문제들에서도 많이 쓰입니다