[JAVA] 백준 1389 플로이드-워셜

 

 

 

 

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

문제

BOJ 유저의 수와 친구 관계가 입력으로 주어졌을 때, 케빈 베이컨의 수가 가장 작은 사람을 구하는 프로그램을 작성하시오.

풀이

이 문제는 친구 관계의 케빈 베이컨의 법칙을 적용하여 거리를 구했을 때 다른 모든 친구로의 거리가 가장 짧은 사람 번호를 구하는 문제이다.

모든 정점들에 대해서 다른 모든 정점으로의 케빈 베이컨 수(거리)를 구해야 하는 문제였기 때문에 플로이드-워셜 알고리즘을 사용하여 문제를 풀었습니다.

📌 입력

        int[][] A = new int[N][N];

        for(int i=1; i<N; i++){
            for(int j=1; j<N; j++){
                if( i==j) A[i][j] = 0;
                else A[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());

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

먼저 자기 자신으로 가는 경로를 0으로 두고 나머진 모든 거리를 충분히 큰 수로 초기화했습니다.

친구 관계가 존재한다면 A → B, 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(A[i][j] > A[i][k] + A[k][j]){
                        A[i][j] = A[i][k] + A[k][j];
                    }
                }
            }
        }

현재 발견된 i → j로 가는 케빈 베이컨의 수(거리)가 i → k, k → j로 경유해서 가는 케빈 베이컨의 수보다 크다면 경유지를 거쳐서 가는 경로로 수정해주었습니다.

📌 케빈 베이컨의 수가 가장 작은사람

        int answer = 1;
        int value = INF;
        for(int i=1; i<N; i++){
            int sum = 0;
            for(int j=1; j<N; j++){
                sum += A[i][j];
            }
            if(value > sum){
                value = sum;
                answer = i;
            }
        }
        System.out.println(answer); 

각 정점들을 돌면서 정점들의 다른 모든 정점으로의 케빈 베이컨 수의 합을 구해 그 값이 가장 작은 정점을 찾아내었습니다.

이렇게 찾은 정점은 케빈 베이컨의 수가 가장 작은 사람이기 때문에 출력해주었습니다.

📌 전체 코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;

class Main {
    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())+1;
        int M = Integer.parseInt(st.nextToken());
        int INF = 100000001;

        int[][] A = new int[N][N];

        for(int i=1; i<N; i++){
            for(int j=1; j<N; j++){
                if( i==j) A[i][j] = 0;
                else A[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());

            A[a][b] = 1;
            A[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(A[i][j] > A[i][k] + A[k][j]){
                        A[i][j] = A[i][k] + A[k][j];
                    }
                }
            }
        }

        int answer = 1;
        int value = INF;
        for(int i=1; i<N; i++){
            int sum = 0;
            for(int j=1; j<N; j++){
                sum += A[i][j];
            }
            if(value > sum){
                value = sum;
                answer = i;
            }
        }
        System.out.println(answer);

    }
}

결과