백준 / 그래프 / 1389번 / 케빈 베이컨의 6단계 법칙 / JS

문제 간단설명

이 문제는 두 사람이 몇 단계 이내에 친구의 친구로 이어질 수 있는지를 나타내는 케빈 베이컨의 수를 계산하고, 케빈 베이컨의 수가 가장 작은 사람을 찾는 문제입니다. 각 사람마다 다른 모든 사람들과 최소 단계로 이어지는 경로를 구한 뒤, 그 경로의 단계 수를 모두 더하여 케빈 베이컨의 수를 계산합니다. 예를 들어, 사람 A와 B가 최소 3단계로 연결된다면, A의 케빈 베이컨 수에는 3이 포함됩니다. 모든 유저의 케빈 베이컨 수를 계산한 뒤, 그 값이 가장 작은 사람을 찾는 것이 문제의 목표입니다.

 

제한 사항

• 2 <= N <= 100
• 1 <= M <= 5000
• 입력 관계:
  • 입력은 각 친구 관계를 나타내며, (A, B) 형식으로 주어집니다.
  • 중복된 친구 관계가 존재할 수 있으며, 자기 자신과 친구인 관계는 없습니다.
  • 모든 사람은 친구 관계로 이어져 있으며, 단절된 그룹은 없습니다.

 

성공 코드

const fs = require('fs');
const filePath = process.platform === 'linux' ? '/dev/stdin' : '../input.txt';
// const filePath = process.platform === 'linux' ? '/dev/stdin' : 'BOJ/input.txt';
const input = fs
  .readFileSync(filePath)
  .toString()
  .trim()
  .split('\n')
  .map((el) => el.trim());

const [N, M] = input.shift().split(' ').map(Number);
const relationList = input.map((row) => row.split(' ').map(Number));

// 인접 행렬
const adjList = {};
// 케빈 베이컨 카운트 인접 행렬
const kevinBaconCountAdjList = Array.from({ length: N + 1 }, () =>
  new Array(N + 1).fill(0)
);

function solution() {
  initAdjList();

  const kevinBaconCountList = getKevinBaconCountList();
  const result = getResult(kevinBaconCountList);

  console.log(result);
}

/**
 * 인접행렬을 초기화 해주는 함수이다.
 */
function initAdjList() {
  for (let i = 1; i <= N; i++) {
    adjList[i] = new Set();
  }

  for (const [user1, user2] of relationList) {
    adjList[user1].add(user2);
    adjList[user2].add(user1);
  }
}

/**
 * bfs를 이용해 각 노드까지의 단계를 구하는 함수이다.
 *
 * @param {number} start 시작 노드
 */
function bfs(start) {
  const queue = [[start, 1]];
  const visited = Array.from({ length: N + 1 }, () => false);

  visited[start] = true;

  while (queue.length > 0) {
    const [curUser, curCount] = queue.shift();

    for (const adjUser of adjList[curUser]) {
      if (visited[adjUser]) {
        continue;
      }

      kevinBaconCountAdjList[curUser][adjUser] = 1;
      kevinBaconCountAdjList[start][adjUser] = curCount;

      visited[adjUser] = true;
      queue.push([adjUser, curCount + 1]);
    }
  }
}

/**
 * 각 유저별 케빈 베이컨수를 구하는 함수이다.
 *
 * @returns 각 유저별 케빈 베이컨수가 담긴 배열
 */
function getKevinBaconCountList() {
  for (let i = 1; i <= N; i++) {
    bfs(i);
  }

  const kevinBaconCountList = kevinBaconCountAdjList.map((row) =>
    row.reduce((acc, cur) => acc + cur)
  );

  return kevinBaconCountList;
}

/**
 * 케빈 베이컨의 수가 가장 작은 사람을 구하는 함수이다.
 *
 * @param {number[]} kevinBaconCountList
 * @returns 케빈 베이커의 수가 가장 작은 사람
 */
function getResult(kevinBaconCountList) {
  const min = Math.min(...kevinBaconCountList.slice(1));
  const minIndex = kevinBaconCountList.indexOf(min);

  return minIndex;
}

solution();

 

인접 리스트를 이용해 문제에서 요구한 그대로 bfs로 구현하였다.

주의할 점은, 중복된 관계도 들어올 수 있기 때문에 Set 자료구조를 사용했다.