1389_케빈 베이컨의 6단계 법칙 ****

사용 알고리즘: 플로이드-워셜

사용 언어: java

 

package di_8_1_그래프의표현;

import java.util.*;

public class Main_bj_1389_케빈베이컨의6단계법칙 {
	static int n, m, friend[][];
	static final int MAX = 100*100+1;

	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		n = sc.nextInt(); //친구 수(n+1)
		m = sc.nextInt(); //관계 수
		
		friend = new int[n+1][n+1];
		for (int i = 0; i < n+1; i++) {
			Arrays.fill(friend[i], MAX);
		}
		for (int i = 0; i < n+1; i++) {
			for (int j = 0; j < n+1; j++) {
				if(i==j) friend[i][j] = 0;
			}
		}
		for (int i = 0; i < m; i++) {
			int a = sc.nextInt();
			int b = sc.nextInt();
			friend[a][b] = 1;
			friend[b][a] = 1;
		}
		
		//
//		for (int i = 0; i < n+1; i++) {
//			System.out.println(Arrays.toString(friend[i]));
//		}
		
		// 플로이드 워셜
		for (int i = 1; i < n+1; i++) {
			for (int k = 1; k < n+1; k++) {
				for (int j = 1; j < n+1; j++) {
					
					int newRelation = friend[i][k] + friend[k][j];
					friend[i][j] = Math.min(friend[i][j], newRelation);
				}
			}
		}
		
		//
//		for (int i = 0; i < n+1; i++) {
//			System.out.println(Arrays.toString(friend[i]));
//		}
		
		int minRel = 100*100 + 1;
		int answer = 0;
		
		for (int i = 1; i < n+1; i++) {
			int sum = 0;
			for (int j = 1; j < n+1; j++) {
				sum += friend[i][j];
			}
			
			if(minRel > sum) {
				minRel = sum;
				answer = i;
			}
		}
		
		System.out.println(answer);
	}

}

 

 

플로이드-워셜은

중간 지점(k)가 최상위 for문으로 들어가야 한다!!