[백준] 1389 케빈 베이컨의 6단계 법칙 - BFS(넓이우선탐색) JAVA

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

코드설명

BFS(넓이우선탐색)을 활용합니다.

 

각 노드에서 BFS를 돌면서 각 노드까지의 최단거리를 구하는 문제였습니다.

그리고 그 최단거리를 모두 더해서 가장 짧은 거리인 노드의 위치를 출력합니다.

 

최단경로 알고리즘인 플로이드-워셜이나 다익스트라 알고리즘도 사용할 수 있을 것으로 보입니다.

다만 이 문제에서는 플로이드-워셜이 훨씬 적합합니다.

플로이드-워셜은 모든 정점에서의 모든 정점까지의 거리를 구할 수 있고, 다익스트라 알고리즘의 경우 한 정점에서 다른 모든 정점까지의 최단거리를 구하기에 그렇지요.

코드

package Main;
 
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.LinkedList;
import java.util.Queue;
import java.util.StringTokenizer;
 
public class Main {
	static int N, M, S, P, A, B, X, L, R, C, n, k, m, l, K;
	static int answer = 100 * (100 + 1) / 2;
	static int[][] dist = new int[101][101];
	static int[][] matrix = new int[101][101];
	public static void main(String[] args) throws IOException{
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());

		N = Integer.parseInt(st.nextToken());
		M = Integer.parseInt(st.nextToken());
		for(int i=0; i<101; i++) {
			Arrays.fill(dist[i], -1);
		}
		for(int i=0;i<M;i++) {
			st = new StringTokenizer(br.readLine());
			int A = Integer.parseInt(st.nextToken()) - 1;
			int B = Integer.parseInt(st.nextToken()) - 1;
			matrix[A][B] = matrix[B][A] = 1;
		}
		
		for(int i=0; i<N; i++) {
			BFS(i);
		}
		
		int answerIdx = -1;
		for(int i=0; i<N; i++) {
			int temp = 0;
			for(int j=0; j<N; j++) {
				temp += dist[i][j];
			}
			if(answer > temp) {
				answer = temp;
				answerIdx = i + 1;
			}
		}
		System.out.println(answerIdx);
	}
	
	static void BFS(int src) {
		Queue<int[]> q = new LinkedList<>();
		q.offer(new int[] {src, 0});
		dist[src][src] = 0;
		
		while(!q.isEmpty()) {
			int[] temp = q.poll();
			int nowNode = temp[0];
			int cnt = temp[1];
			
			for(int connect = 0; connect < matrix[nowNode].length; connect++) {
				if(matrix[nowNode][connect] == 1 && dist[src][connect] == -1) {
					dist[src][connect] = cnt + 1;
					q.offer(new int[] {connect, cnt + 1});
				}
			}
		}
		
	}
	
}