백준 1389 : 케빈 베이컨 6단계 법칙

🔍 문제

모든 사람간의 최단거리 구하기

 

플로이드 워셜 사용해서 푸는건 알았는데 자꾸 답이 안나오는거...

 

👾 코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.StringTokenizer;

public class P1389 {
    public static void main(String[] args) throws IOException {
        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()); //관계 수
        int[][] FW = new int[N+1][N+1]; //

        // 배열 초기화
        for(int i = 1; i <= N; i++) {
            Arrays.fill(FW[i], 99999999);
            FW[i][i] = 0;
        }

        //가중치 저장
        for(int i = 0; i < M; i++) {
            st = new StringTokenizer(br.readLine());
            int a = Integer.parseInt(st.nextToken());
            int b = Integer.parseInt(st.nextToken());
            FW[a][b] = 1;
            FW[b][a] = 1;
        }

        //플로이드 워셜 점화실 사용한 반복문(최단거리 배열 채우기)
        for(int K = 1; K <= N; K++) {
            for(int S = 1; S <= N; S++) {
                for(int E = 1; E <= N; E++) {
                    FW[S][E] = Math.min(FW[S][E], FW[S][K] + FW[K][E]);
                }
            }
        }

        int result = 1;
        int minSum = Integer.MAX_VALUE;
        for(int i = 1; i <= N; i++) {
            int sum = 0;
            for(int j = 1; j <= N; j++) {
                sum+=FW[i][j];
            }
            if(sum < minSum) {
                minSum = sum;
                result = i;
            }
        }
        System.out.println(result);
    }
}

 

💡 처음 배열 초기화  Integer.MAX_VALUE  ➡️  99,999,999

처음에 배열 초기화할 때 INF값을 Integer.MAX_VALUE값으로 설정했는데 자꾸 배열에 음수 값이 들어가고 답도 이상하게 나옴...

FW[S][K]와 FW[K][E] 둘 중 하나가 Integer.MAX_VALUE인 경우, 이를 더하면 값이 Integer.MAX_VALUE + 1 이상으로 오버플로우가 발생해 음수가 된다.

 

항상 오버플로우 조심하긔~⭐️⭐️