문제링크
실버 1
그래프 탐색
N의 케빈 베이컨 수는 N을 제외한 다른 유저와 만나기 위해 거쳐야할 각각의 단계수의 합을 말한다.
BOJ의 유저중 케빈 베이컨 수가 가장 작은 사람을 구하시오.
유저의 수 N
친구 관계의 수 M
친구 관계 A,B (M줄)
케빈 베이컨 수가 가장 작은 사람을 출력한다.
겹치는경우 가장 작은 사람을 출력
import java.util.*;
public class 백준1389 {
static int n,m,cnt=0,answer=0;
static int[][] arr;
static int MIN=Integer.MAX_VALUE;
static int[] visited;
static Scanner scan =new Scanner(System.in);
static StringBuilder sb=new StringBuilder();
public static void main(String[] args) {
// 입력
n=scan.nextInt();
m=scan.nextInt();
arr=new int[n+1][n+1];
for(int i=0;i<m;i++) {
int a=scan.nextInt();
int b=scan.nextInt();
arr[a][b]=1;
arr[b][a]=1;
}
for(int i=1;i<=n;i++) { //각자의 베이컨 수 구하기
int ans=0;
visited=new int[n+1];
bfs(i);
for(int j=1;j<=n;j++) {
ans+=visited[j];
}
if(MIN>ans-1) {
answer=i;
MIN=ans-1;
}
}
System.out.print(answer);
}
static void bfs(int i) {
Queue<Integer>q =new LinkedList<>();
q.offer(i);
visited[i]=1;
while(!q.isEmpty()) {
int nxt=q.poll();
for(int a=1;a<=n;a++) {
if(arr[nxt][a]==1&&visited[a]==0) {
visited[a]=visited[nxt]+1;
q.offer(a);
}
}
}
}
}