케빈 베이컨의 6단계 법칙

문제

언어

  • JavaScript

순서도

  1. 친구 관계에서 중복 제거하고, 인접리스트 생성
  2. 각 사람마다 BFS 탐색을 통해서 케빈 베이컨 수 구하기
  3. 케빈 베이컨 수가 최소인 사람 출력

문제 풀이 step 1

  • 케빈 베이컨의 6단계 법칙
    • 지구에 있는 모든 사람들은 최대 6단계 이내에서 서로 아는 사람으로 연결될 수 있습니다.
  • 케빈 베이컨 게임은 임의의 두 사람이 최소 몇 단계 만에 이어질 수 있는지 계산하는 게임입니다.
  • 사람의 수와 각 사람의 친구 관계가 주어질 때, 케빈 베이컨 수가 최소인 사람을 구하는 문제입니다.

문제 풀이 step 2

  • 우선, BFS 탐색을 하기 위해서 친구 관계를 인접리스트 형식으로 만듭니다.
    • 이 때, 친구 관계는 중복되어 들어올 수 있기 때문에 중복 제거를 수행해줍니다.
  • 인접리스트를 만들었다면, 각 사람마다 BFS 탐색을 통해서 케빈 베이컨 수를 구합니다.
    • 이 때, 방문처리 대신에 연결 단계를 표시합니다.
    • 탐색을 시작한 사람으로부터 각 사람과의 연결 단계를 모두 더하면 케빈 베이컨 수를 구할 수 있습니다.
  • n 명의 사람 중에서 케빈 베이컨 수가 가장 작은 사람을 구하면 정답입니다.
    • 이 때, 케빈 베이컨 수 가장 작은 사람이 여러 명이라면, 번호가 가장 작은 사람을 구하면 됩니다.
  • 추가 설명은 주석으로 작성하겠습니다.

소스 코드

const input = require("fs")
	.readFileSync("/dev/stdin")
	.toString()
	.trim()
	.split("\n");

class Queue {
	constructor() {
		this.bucket = [];
		this.front = -1;
		this.rear = -1;
	}

	enqueue(data) {
		this.bucket[++this.rear] = data;
	}

	dequeue() {
		return this.bucket[++this.front];
	}

	isEmpty() {
		return this.front === this.rear;
	}
}

const bfs = (relations, distance, start) => {
	const queue = new Queue();

	distance[start] = 0;
	queue.enqueue(start);

	let kevinBaconNum = 0;
	while (!queue.isEmpty()) {
		const from = queue.dequeue();

		for (let i = 0; i < relations[from].length; i++) {
			const to = relations[from][i];

			if (distance[to] !== -1) continue;

			// 방문처리 대신에 연결 단계 표시
			distance[to] = distance[from] + 1;
			queue.enqueue(to);

			// 케빈 베이컨 수 구하기
			kevinBaconNum += distance[to];
		}
	}

	return kevinBaconNum;
};

const solution = (input) => {
	const [n, m] = input[0].split(" ").map(Number);

	const relations = Array.from({length: n + 1}, () => []);

	for (let i = 1; i < 1 + m; i++) {
		const [from, to] = input[i].split(" ").map(Number);

		// 친구 관계 중복 제거
		let overlap = false;
		for (let j = 0; j < relations[from].length; j++) {
			if (relations[from][j] === to) {
				overlap = true;
				break;
			}
		}

		if (overlap) continue;

		relations[from].push(to);
		relations[to].push(from);
	}

	let ans = 0;
	let min = Number.MAX_SAFE_INTEGER;
	for (let i = 1; i < n + 1; i++) {
		const distance = Array(n + 1).fill(-1);

		const kevinBaconNum = bfs(relations, distance, i);

		// 케빈 베이컨 수가 가장 작은 사람 찾기
		if (min > kevinBaconNum) {
			ans = i;
			min = kevinBaconNum;
		}
	}

	return ans;
};

console.log(solution(input));