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

· May 15, 2022
Java
```import java.io.BufferedOutputStream;
import java.io.IOException;
import java.io.PrintWriter;
import java.util.*;

public class Main {

public static PrintWriter out = new PrintWriter(new BufferedOutputStream(System.out));
public static MyScanner sc = new MyScanner();

static int pi(String s) {
return Integer.parseInt(s);
}

public static class MyScanner {
StringTokenizer st;

public MyScanner() {
}

String next() {
while (st == null || !st.hasMoreElements()) {
try {
} catch (IOException e) {
e.printStackTrace();
}
}
return st.nextToken();
}

int nextInt() {
return Integer.parseInt(next());
}

long nextLong() {
return Long.parseLong(next());
}

double nextDouble() {
return Double.parseDouble(next());
}

String nextLine() {
String str = "";
try {
} catch (IOException e) {
e.printStackTrace();
}
return str;
}

}

static int n;
static int bacon(int start, boolean[][] arr){
int[] visited = new int[n+1];
for(int i=1; i<=n; i++){
visited[i] = -1;
}
visited[start] = 0;
while(!q.isEmpty()){
int now = q.poll();
for(int i=1; i<=n ;i++){
if(arr[now][i]==true&&visited[i]==-1){
visited[i] = visited[now]+1;
}
}
}
int sum = 0;
for(int i=1; i<=n; i++){
sum += visited[i];
}
return sum;
}
public static void main(String[] args) throws Exception {
n = sc.nextInt();
int m = sc.nextInt();
boolean[][] arr = new boolean[n+1][n+1];
for(int i=0; i<m; i++){
int a = sc.nextInt(), b = sc.nextInt();
arr[a][b] = true;
arr[b][a] = true;
}
int[] arrr = new int[n+1];

for(int i=1; i<=n; i++){
arrr[i] = bacon(i, arr);
}

int min = 1;
for(int i=1; i<=n; i++){
if(arrr[i]<arrr[min]){
min = i;
}
}
out.println(min);
out.flush();
}
}```
Output
`(Run the program to view its output)`