[백준 1389] 케빈 베이컨의 6단계 법칙 (JAVA)

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

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

 

이 문제는 두가지 방법으로 해결가능하다.

1) BFS

2) 플로이드 워셜

https://chanhuiseok.github.io/posts/algo-50/

알고리즘 - 플로이드-워셜(Floyd-Warshall) 알고리즘

 

 

 

1. BFS

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

public class Main {
	static int[][] arr;
	static boolean[] visited;
	static int n;
	static int mincount = Integer.MAX_VALUE;
	static int min = 0;

	public static void main(String[] args) throws NumberFormatException, IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());
		n = Integer.parseInt(st.nextToken());
		int m = Integer.parseInt(st.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] = 5001;
			}
		}
		for (int i = 0; i < m; i++) {
			st = new StringTokenizer(br.readLine());
			int x = Integer.parseInt(st.nextToken());
			int y = Integer.parseInt(st.nextToken());
			arr[x][y] = 1;
			arr[y][x] = 1;
		}
		
		for(int i=1;i<=n;i++) {
			visited=new boolean[n+1];
			bfs(i);
		}
		System.out.println(min);
	}

	
	private static void bfs(int i) {
		Queue<Item> q = new LinkedList<>();
		q.offer(new Item(i,0));
		visited[i]=true;
		int count=0;
		while(!q.isEmpty()) {
			Item item= q.poll();
			count+=item.count;
			for(int j=1;j<=n;j++) {
				if(arr[j][item.idx]==1&&!visited[j]) {
					visited[j]=true;
					q.offer(new Item(j,item.count+1));
				}
			}
		}
		if(mincount>count) {
			mincount=count;
			min=i;
		}else if(mincount==count) {
			min=Math.min(i, min);
		}
	}
	
	static class Item{
		int idx;
		int count;
		Item(int idx,int count){
			this.idx=idx;
			this.count=count;
		}
	}
}

 

 

 

2. 플로이드 워셜

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

public class Main {
	static int[][] arr;
	static int n;

	public static void main(String[] args) throws NumberFormatException, IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());
		n = Integer.parseInt(st.nextToken());
		int m = Integer.parseInt(st.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] = 5001;
			}
		}
		for (int i = 0; i < m; i++) {
			st = new StringTokenizer(br.readLine());
			int x = Integer.parseInt(st.nextToken());
			int y = Integer.parseInt(st.nextToken());
			arr[x][y] = 1;
			arr[y][x] = 1;
		}
		
		floyd();
		
		int mincount = Integer.MAX_VALUE;
		int min = 0;
		
		for (int i = 1; i <= n; i++) {
			int count = 0;
			for (int j = 1; j <= n; j++) {
				count += arr[i][j];
			}
			if (mincount > count) {
				min = i;
				mincount=count;
			} else if (mincount == count) {
				min = Math.min(i, min);
			}
		}
		System.out.println(min);
	}

	private static void floyd() {
		for (int k = 1; k <= n; k++) { // 거쳐가는 중간 지점 노드
			for (int i = 1; i <= n; i++) { // 시작 노드
				for (int j = 1; j <= n; j++) { // 도착 노드
					arr[i][j] = Math.min(arr[i][k] + arr[k][j], arr[i][j]); // 최단경로 초기화
				}
			}
		}
	}
}