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

Java

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

문제

케빈 베이컨의 6단계 법칙에 의하면 지구에 있는 모든 사람들은 최대 6단계 이내에서 서로 아는 사람으로 연결될 수 있다.
케빈 베이컨 게임은 임의의 두 사람이 최소 몇 단계 만에 이어질 수 있는지 계산하는 게임이다.

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

접근 방법

플로이드 워셜을 이용하여, 각 사람마다 다른 사람까지 이어지는 단계를 구한다.
n명의 사람 중, 케빈 베이컨의 수가 제일 적은 사람을 구한다.

코드

import java.util.*;
import java.io.*;

public class Main {
	static int n, m, result, min = Integer.MAX_VALUE, a, b;
	static final int MAX = 987654321;
	static int[][] arr;
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    	StringTokenizer stk = new StringTokenizer(br.readLine());
    	n = stoi(stk.nextToken());
    	m = stoi(stk.nextToken());
    	
    	arr = new int[n + 1][n + 1];
    	// ---------- 플로이드 워셜 시작-------------
    	for(int i = 1; i <= n; i++) {
    		for(int j = 1; j <= n; j++) {
    			if(i == j)
    				arr[i][j] = 0;
    			else
    				arr[i][j] = MAX; 
    		}
    	}
    	
    	for(int i = 0; i < m; i++) {
    		stk = new StringTokenizer(br.readLine());
    		a = stoi(stk.nextToken());
    		b = stoi(stk.nextToken());
    		arr[a][b] = 1;
    		arr[b][a] = 1;
    	}
    	// 경유지
    	for(int k = 1; k <= n; k++) {
    		// 출발지
    		for(int i = 1; i <= n; i++) {
    			if(i == k)
    				continue;
    			// 도착지
    			for(int j = 1; j <= n; j++) {
    				if(i == j)
    					continue;
    				if(arr[i][j] > arr[i][k] + arr[k][j])
    					arr[i][j] = arr[i][k] + arr[k][j];
    	    	}
        	}
    	}
		// ---------- 플로이드 워셜 끝-------------
    	int sum = 0;
    	for(int i = 1; i <= n; i++) {
    		sum = 0;
    		for(int j = 1; j <= n; j++) {
    			sum += arr[i][j];
    		}
    		if(min > sum) {
    			min = sum;
    			result = i;
    		}
    	}
    	
    	System.out.println(result);
    	
    	br.close();
	}
	
	static int stoi(String str) {
    	return Integer.parseInt(str);
    }
}	

총평

후기

플로이드 워셜의 응용 문제

개선할 점

없습니다.