이것저것 개발 블로그

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

풀이)

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Map;
import java.util.StringTokenizer;

public class Main_BJ_1389_케빈베이컨의6단계법칙 {
    static int[][] adj;
    static int INF = 10000;
    public static void main(String[] args) throws Exception{
        BufferedReader br =  new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        int n = Integer.parseInt(st.nextToken());
        int m = Integer.parseInt(st.nextToken());
        adj = new int[n+1][n+1];
        for(int i=1; i<=n; i++){
            for(int j=1; j<=n; j++){
                if(i==j)
                    adj[i][j] = 0;
                else
                    adj[i][j] = INF;
            }
        }

        for(int i=0; i<m; i++){
            st = new StringTokenizer(br.readLine());
            int a = Integer.parseInt(st.nextToken());
            int b = Integer.parseInt(st.nextToken());

            adj[a][b] = 1;
            adj[b][a] = 1;
        }


        for(int k=1; k<=n; k++) {
            for (int i = 1; i <= n; i++) {
                for (int j = 1; j <= n; j++) {
                    adj[i][j] = Math.min(adj[i][j], adj[i][k]+adj[k][j]);
                }
            }
        }

        int min = 0;
        int sum = Integer.MAX_VALUE;
        for(int i=1; i<=n; i++){
            int temp = 0;
            for(int j=1; j<=n; j++){
                if(j != i) {
                    temp += adj[i][j];
                }
            }
            if(sum > temp){
                sum = temp;
                min = i;
            }
        }

        System.out.println(min);
    }//main
}

플로이드-워셜로 풀었는데 몇 번의 시도가 실패했다.

첫 번째는, 플로이드 워셜 개념을 다시 상기시켜야 할 필요성...

두 번째는, 큰 값으로 갱신할 때 Integer.MAX_VALUE로 하지 말아야 한다는 것이다.(그냥 충분하게 큰 값이면 된다)

아무 생각 없이 Integer.MAX_VALUE로 했다가 둘이 더해지면 값이 넘어가 음수값이 되어버려서 계산을 할 수 없었다.

(플로이드 워셜은 가중치가 모두 양수여야 하니까!!)

다음엔 한 번에 잘 풀어봤으면 좋겠다.

그리고 당연히 bfs로도 풀 수 있다!!!