[1389] 케빈 베이컨의 6단계 법칙

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

---

import java.util.Scanner;
import java.util.ArrayList;
import java.util.LinkedList;
import java.util.Queue;

public class Main {
	
	static int N, M, cabin;
	static ArrayList<Integer>[] list;
	static Queue<Pair> queue;
	static boolean[] visited;
	
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		N = sc.nextInt();
		M = sc.nextInt();
		list = new ArrayList[N+1];
		
		for(int i=0; i<=N; i++) {
			list[i] = new ArrayList();
		}
		
		for(int i=0; i<M; i++) {
			int A = sc.nextInt();
			int B = sc.nextInt();
			list[A].add(B);
			list[B].add(A);
		}
		
		int min = 99999999;
		int answer = 0;
		for(int i=1; i<=N; i++) {
			queue = new LinkedList<Pair>();
			visited = new boolean[N+1];
			queue.offer(new Pair(i, 0));
			cabin = 0;
			
			BFS();
			
			if(cabin < min) {
				min = cabin;
				answer = i;
			}
			
		}
		System.out.println(answer);
		
	}
	
	public static void BFS() {
		
		while(!queue.isEmpty()) {
			Pair p = queue.poll();
			cabin += p.cnt;
			
			visited[p.x] = true;
			
			for(int i=0; i<list[p.x].size(); i++) {
				int nx = list[p.x].get(i);
				if(!visited[nx]) {
					queue.offer(new Pair(nx, p.cnt+1));
					visited[nx]=true;
				}

			}
			
		}
	}
	
}

class Pair {
	int x;
	int cnt;
	
	Pair(int x, int cnt){
		this.x=x;
		this.cnt=cnt;
	}
}

---

정답률이 높아서 간단한 DFS, BFS 문제 인줄 알았는데 처음 풀었을 때 생각보다 어떻게 풀지 모르겠어서 고민을 많이 했던 문제였던 것 같습니다. 유저의 수와 친구 관계의 수가 주어지면 각 유저에서 모든 친구까지 최소한으로 갈 수 있는 숫자를 모두 더한 값이 '케빈 베이컨의 수' 라고 하는데 그 케빈의 값이 가장 작은 유저를 구하는 문제입니다. 저는 Pair 라는 class 를 선언해서 x는 유저의 번호를 나타내고 cnt 는 유저에서 BFS를 시작하는데 다른 친구 까지 갈 때 1씩 더해줘서 최소한의 수를 나타내 더해서 케빈값을 구하기 위해 선언했습니다. 그래서 케빈값이 가장 작은 유저를 출력해서 정답을 구했습니다.

[ 문제 풀이 ]

1. 유저와 친구의 관계를 ArrayList 배열에 저장했습니다. 그럼 ArrayList 배열의 인덱스는 유저의 번호를 나타내고 그 번호와 연결돼 있는 친구들은 각 ArrayList의 배열 인덱스에 들어가있습니다.

2. 이제 1번부터 N 번의 친구까지 각 자리에서 BFS 를 하는데 Queue 에 넣어 줄 때마다 Pair 클래스의 cnt 에 1씩 더해줘서 다음 BFS 를 실행하여 그 사람을 pop 할 때 cnt를 cabin이라는 변수에 계속 더해주어서 케빈값을 구했습니다.

3. 한번 실행할 때 마다 비교해서 케빈 값의 최솟값을 구하고, 그 때 인덱스를 저장해서 유저를 출력하면 정답입니다.