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

 

예제에 나온대로 BOJ의 유저들간의 관계를 선으로 이어보면 아래와 같다

 

1번이 2,3,4,5번 까지 각각 몇 단계를 거쳐야 하는지의 합
2번이 1,3,4,5번 까지 각각  몇 단계를 거쳐야 하는지의 합
3번이 1,2,4,5번 까지 각각  몇 단계를 거쳐야 하는지의 합
4번이 1,2,3,5번 까지 각각  몇 단계를 거쳐야 하는지의 합
5번이 1,2,3,4번 까지 각각   단계를 거쳐야 하는지의 합
를 구하면 된다.

즉,
1→2, 1→3, 1→4, 1→5 최소 거리의 합
2→1, 2→3, 2→4, 2→5 최소 거리의 합
3→1, 3→2, 3→3, 3→4 최소 거리의 합
4→1, 4→2, 4 →3, 4→5 최소 거리의 합
5→1, 5→2, 5 →3, 5→4 최소 거리의 합
을 구하면 된다

각 최소 거리는 BFS를 사용하면 된다.

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.ArrayList;
import java.util.LinkedList;
import java.util.Queue;
import java.util.StringTokenizer;

public class Main {
	static int n;
	static int m;
	static ArrayList<Integer>[] relations;

	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
		StringTokenizer st = new StringTokenizer(br.readLine());
		n = Integer.parseInt(st.nextToken()); // 유저 수
		m = Integer.parseInt(st.nextToken()); // 친구 관계 수
		relations = new ArrayList[n + 1]; // 친구관계 그래프

		// 그래프 초기화
		for (int i = 1; i <= n; i++) {
			relations[i] = new ArrayList<>();
		}

		// 그래프 입력
		for (int i = 1; i <= m; i++) {
			st = new StringTokenizer(br.readLine());
			int u = Integer.parseInt(st.nextToken());
			int v = Integer.parseInt(st.nextToken());
			relations[u].add(v);
			relations[v].add(u);
		}

		int minValue = Integer.MAX_VALUE; // 최소 케빈 베이컨 값
		int minValueIndex = -1; // 최소 케빈 베이컨 값인 사람의 번호

		// 각 사람마다 BFS 수행
		for (int i = 1; i <= n; i++) {
			// 케빈 베이컨 값 구하기
			int kevinBaconNumber = KevinBacon(i);

			// 최소 케빈 베이컨 값인지 확인
			if (kevinBaconNumber < minValue) {
				minValue = kevinBaconNumber;
				minValueIndex = i;
			}
		}

		bw.write(String.valueOf(minValueIndex));
		bw.flush();
		bw.close();
	}

	// start로부터 모든 사람까지의 최단 거리를 구하는 BFS 메소드
	private static int KevinBacon(int start) {
		boolean[] visited = new boolean[n + 1]; // 방문 배열
		int[] distance = new int[n + 1]; // 각 사람까지 거리 저장하는 배열
		int sum = 0;
		Queue<Integer> queue = new LinkedList<>();

		queue.add(start);
		visited[start] = true;
		distance[start] = 0;

		while (!queue.isEmpty()) {
			int current = queue.poll();
			for (int neighbor : relations[current]) {
				if (!visited[neighbor]) {
					// 방문 처리
					visited[neighbor] = true;

					// 거리 값 구하기
					int d = distance[current] + 1;
					distance[neighbor] = d;
					// 케빈베이컨 값 더하기
					sum += d;

					// bfs 큐 삽입
					queue.add(neighbor);
				}
			}
		}

		return sum;
	}
}