[Java] 백준 1389번: 케빈 베이컨의 6단계 법칙

문제

💡 일단 생각하기!

백준 BFS, DFS 문제를 검색해서 나온 문제집에서 푼거라 당연히 BFS일줄 알았다..!! 중간에 DFS로 바꿨는데도 풀리지 않아 풀이를 참고했는데 백만년전에 배운(사실 반년 전) 플로이드-워셜로 푸는 문제였던 것이다 (...)
N의 범위가 작기 때문에 시간 복잡도는 O(N^3)인 플로이드-워셜로 풀이가 가능하다. 자세한 개념은 이 블로그를 참고하여 익혔다.

아무튼 넣을 수 있는 가장 큰 수를 배열에 넣어놓고 i=j일때는 0을 넣는다. 그리고 관계가 있는 것들은 가중치 1을 넣는다. 플로이드-워셜을 사용해서 가중치를 계산해주고 인덱스별로 값을 더해서 가장 적은 값을 출력하면 끝!

풀이

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

/**
 * 백준 1389번 케빈 베이컨의 6단계 법칙
 * 메모리 : 12216KB 시간 : 100ms
 * 
 * 아이디어
 * - 이 문제도 BFS 또는 DFS로 풀이하는 줄 알았는데 플로이드 워셜로 푸는거였다 (..)
 * - 배열을 INF로 초기화 해준 뒤, A = B인 값은 0을 넣어준다 => A와 B가 같을 수 없기 때문!
 * - X에서 Y로 가는 최단 경로 = X에서 중간 노드로 가는 경로 + 중간 노드에서 Y로 가는 경로
 * 
 */
public class BJ_1389_케빈베이컨의6단계법칙_김유나 {
	static final int INF = 987654321;
	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());
		int m = Integer.parseInt(st.nextToken());
		
		int arr[][] = new int[n + 1][n + 1];
		
		for (int i = 1; i <= n; i++) {
			for (int j = 1; j <= n; j++) {
				arr[i][j] = INF; // INF로 모두 초기화
				
				if (i == j) arr[i][j] = 0; // i=j일 경우에만 0
			}
		}
		
		for (int i = 0; i < m; i++) {
			st = new StringTokenizer(br.readLine());
			int a = Integer.parseInt(st.nextToken());
			int b = Integer.parseInt(st.nextToken());
			
			arr[a][b] = arr[b][a] = 1; // 가중치 1
		}
		
		// 플로이드 워셜
		for (int k = 1; k <= n; k++) {
			for (int i = 1; i <= n; i++) {
				for (int j = 1; j<= n; j++) {
					if (arr[i][k] + arr[k][j] < arr[i][j]) {
						arr[i][j] = arr[i][k] + arr[k][j];
					}
				}
			}
		}
		
		
		int min = INF;
		int minIdx = INF;
		for (int i = 1; i <= n; i++) {
			int sum = 0;
			for (int j = 1; j <= n; j++) {
				sum += arr[i][j];
			}
			
			if (min > sum) {
				min = sum;
				minIdx = i;
			}
		}
		
		System.out.println(minIdx);
	}
}