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

문제

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

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

 

코드

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

class Main {	
	static ArrayList<Integer> graph[];
	static int n, m;
	public static void main(String args[]) throws Exception{
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));		
		StringTokenizer st = new StringTokenizer(br.readLine());
		
		n = Integer.parseInt(st.nextToken());
		m = Integer.parseInt(st.nextToken());
		
		graph = new ArrayList [n+1];
		
		for(int i=0;i<=n;i++) {
			graph[i] = new ArrayList<>();
		}
		
		for(int i=0;i<m;i++) {
			st = new StringTokenizer(br.readLine());
			int a = Integer.parseInt(st.nextToken());
			int b = Integer.parseInt(st.nextToken());
			
			graph[a].add(b);
			graph[b].add(a);
		}
		
		int answer = 0;
		int min = Integer.MAX_VALUE;
		
		for(int i=1;i<=n;i++) {
			if(min > bfs(i)) {
				min = bfs(i);
				answer = i;
			}
		}
		
		System.out.println(answer);
		
	}
	
	static public int bfs(int start) {
		Queue<Integer> que = new LinkedList<>();
		int visited[] = new int [n+1];
		Arrays.fill(visited, -1);
		int count = 0;
		
		que.add(start);
		visited[start] = 0;
		while(!que.isEmpty()) {
			int cur = que.poll();
			
			for(int next : graph[cur]) {
				if(visited[next] == -1 ) {
					visited[next] = visited[cur]+1;
					que.add(next);
				}
			}
		}
		
		for(int i=1;i<=n;i++) {
			count += visited[i];
		}
		
		return count;
		
		
	}
	
}