문제 이해

케빈 베이컨의 수라는 것이 존재한다.

A와 직접적으로 아는 지인은 1 단계의 케빈 베이컨의 수를 가진다.
A와 B가 x단계의 지인을 거쳐 아는 사이일 경우, x+1의 케빈 베이컨 수를 가진다.
(중간 node가 x라는 의미이므로, 중간 edge는 x+1이 될 것이다)

직접적인 지인(인접한 점들)의 리스트가 나올 것이다.
이 때, 가장 적은 케빈 베이컨의 수를 가진 사람을 출력하는 문제이다.

---

문제 풀이

그래프에서 A ⇒ B 점으로 가는 최소의 Edge를 구하는 문제이다.

A,B,C,D라는 사람이 존재할 때, A의 케빈 베이컨 수는 (A⇒B 경로 중 최소 Edge 개수) + (A⇒C 경로 중 최소 Edge 개수) + (A⇒D 경로 중 최소 Edge 개수)일 것이다.

가중치가 없는 그래프에서 한 점에서 다른 모든 점까지의 최소 거리 합을 구하는 문제이다. 따라서 BFS를 통해 문제를 해결했다.

• 참고로 더 효율적인 방법은, 이 그래프는 무방향 그래프이므로 A⇒B 경로 중 최소 edge개수와 B⇒A 경로 중 최소 edge 개수는 같다. 따라서, A의 경우 (B,C,D)만, B의 경우 (C,D)만, C의 경우 D와의 거리만을 계산해도 문제를 해결할 수 있다.

하지만 시간적 제한에 큰 문제가 없으므로 모든 node들에 계산을 수행했다.

---

코드

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

class Count{
	int friend;
	int length;
	
	public Count(int friend, int length) {
		this.friend = friend;
		this.length = length;
	}
}

public class Main {
	static StringBuilder sb = new StringBuilder();
	static int N,M;
	static ArrayList<Integer>[] friends;
	
	static Integer bfs(int start) {
		Queue<Count> queue = new LinkedList<>();
		
		queue.add(new Count(start,0));
	
		int ans = 0;
		boolean[] visit = new boolean[N+1];
		
		while(!queue.isEmpty()) {
			Count tmp = queue.poll();
			if(visit[tmp.friend]) continue; 
            // 이미 방문한 점. 중복 처리할 필요가 없다.
			
			visit[tmp.friend] = true; 
			ans+=tmp.length; 
            // BFS의 간선 거리 특징. 
            // 처음 방문한 점에 저장된 거리가 최소 거리이므로, 케빈 베이컨 수이다
			
			for(int s:friends[tmp.friend]) {
				queue.add(new Count(s, tmp.length+1));
			}
		}
		return ans;
	}
	
	public static void main(String[] args) {

		FastReader sc = new FastReader();
		
		N = sc.nextInt();
		M = sc.nextInt();
		friends = new ArrayList[N+1];
		
		for(int i = 1;i<N+1;i++) {
			friends[i] = new ArrayList<>();
		}
		
		for(int i =0;i<M;i++) {
			int tmp1 = sc.nextInt();
			int tmp2 = sc.nextInt();
			
			friends[tmp1].add(tmp2);
			friends[tmp2].add(tmp1);
		}
		
		int[] ans = new int[N+1];
		for(int i =1;i<N+1;i++) {
			ans[i] = bfs(i);
		}
		
		int min = Integer.MAX_VALUE;
		int index = -1;
		for(int i =1;i<N+1;i++) {
			if(min > ans[i]) {
				min = ans[i];
				index=  i;
			}
		}
		
		System.out.println(index);
	}
	
	static class FastReader // 빠른 입력을 위한 클래스
}

---

결과