[BOJ_1389 | Floyd]케빈 베이컨의 6단계 법칙

풀이

플로이드 와샬 알고리즘을 조금만 응용할 수 있다면 쉽게 해결되는 문제이다.

그래프의 가중치를 저장하는 dis 배열과 같이 동작하는 count배열을 추가하였다.

이 count 배열은 dis 배열이 갱신될 때마다 중간에 얼마나 많은 정점들이 연결되는 지를 

카운트하여 저장하는 배열이다.

예를들어

1 - 2 를 연결하는 가중치를 나타내는  dis[1][2] 값이

1 - 3 - 2로 갱신될 때 count[1][2]값이  count[1][3] + count[3][2] 값으로 갱신되는 것이다.

이렇게 모든 점에 대해서 플로이드 알고리즘을 한바퀴 돌고 나면, 

dis배열과 count배열이 갱신되게 되고

각각의 count값을 i값에 대해 합을 낸 것을 구하면, 각 i 값에 따른 케빈 베이컨의 수가 나오게 된다.

정리하면, 배열 변수를 하나 추가하여

 간단한 플로이드 와샬 알고리즘의 응용을 통해 해결할 수 있는 문제이다.

소스 코드

import java.util.*;
public class BOJ_1389 {
    public static void main(String[] args){
        Scanner input = new Scanner(System.in);
        int n = input.nextInt(); int m = input.nextInt();
        int[][] dis = new int[n][n];
        int[][] count = new int[n][n];
        for(int i=0;i<n;i++){
            for(int j=0;j<n;j++){
                dis[i][j] = 100;
                count[i][j] = 1;
            }
        }
        for(int i=0;i<m;i++){
            int i1 = input.nextInt();
            int j1 = input.nextInt();
            dis[i1-1][j1-1] = 1;
            dis[j1-1][i1-1] = 1;
        }
 
        //floyd
        for(int k=0;k<n;k++){
            for(int i=0;i<n;i++){
                for(int j=0;j<n;j++){
                    if(dis[i][j]>dis[i][k]+dis[k][j]){
                        dis[i][j] = dis[i][k]+dis[k][j];
                        count[i][j] = count[i][k]+count[k][j];
                    }
                }
            }
        }
        int minVal = Integer.MAX_VALUE;
        int minAddr = 0;
        for(int i=0;i<n;i++){
            int sum = 0;
            for(int j=0;j<n;j++){
                sum+=dis[i][j];
            }if(sum<minVal){minVal = sum; minAddr = i+1;}
        }System.out.println(minAddr);
    }
}