케빈 베이컨의 6단계 법칙 [백준 1389][실버1][Java]

 

[광고 누르면 오늘의 행운 상승!!]

https://www.acmicpc.net/problem/1389

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

그래프 문제  
플로이드 알고리즘을 사용하여 풀었다. 
하지만 플로이드 알고리즘은 O(n^3) 이기 때문에 BFS로 푸는 방법을 생각해 봐야함

package Study0227;

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

public class 케빈베이컨의6단계법칙 {
	static int map[][] = new int[101][101];
	static int N,M,ans;
	static int Min = Integer.MAX_VALUE;
	public static void main(String[] args)  throws Exception{
		System.setIn(new FileInputStream("test.txt"));
		Scanner sc = new Scanner(System.in);
		N = sc.nextInt();
		M = sc.nextInt();
		
		 for (int i = 0; i < N; i++) 
		        for (int j = 0; j < N; j++) 
		            if(i!=j)map[i][j] = 999999;


		for (int j = 0; j < M; j++) {
			
			int row = sc.nextInt()-1;
			int col = sc.nextInt()-1;
			map[row][col] = 1;
			map[col][row] = 1;
		}

		for (int k = 0; k < N; k++) {
	        for (int i = 0; i < N; i++) {
	            for (int j = 0; j < N; j++) {
	                if (map[i][j] > map[i][k] + map[k][j])
	                    map[i][j] = map[i][k] + map[k][j];
	            }
	        }
	    }//플로이드 와샬 알고리즘 All pair Shortest Path 알고리즘.

		for (int i = 0; i < N; i++) {
			int temp = 0;
			for (int j = 0; j < N; j++) {
				temp += map[i][j];
			}
			if(Min > temp) {
				Min = temp;
				ans = i;
			}
		}
		System.out.println(ans+1);
	}
}

//1 3
//1 4
//2 3
//3 4
//4 5
.