[JavaScript] 백준 1389번: 케빈 베이컨의 6단계 법칙 (플로이드 워셜, BFS)

난이도 : 실버 1
알고리즘 유형 : 플로이드 워셜, 너비 우선 탐색
문제 링크 : https://www.acmicpc.net/problem/1389

 

 

문제

케빈 베이컨 게임은 임의의 두 사람이 최소 몇 단계 만에 이어질 수 있는지 계산하는 게임이다.

케빈 베이컨 수는 모든 사람과 케빈 베이컨 게임을 했을 때, 나오는 단계의 합이다.

예를 들어, BOJ의 유저가 5명이고, 1과 3, 1과 4, 2와 3, 3과 4, 4와 5가 친구인 경우를 생각해보자.

1은 2까지 3을 통해 2단계 만에, 3까지 1단계, 4까지 1단계, 5까지 4를 통해서 2단계 만에 알 수 있다. 따라서, 케빈 베이컨의 수는 2+1+1+2 = 6이다.

입력

첫째 줄에 유저의 수 N (2 ≤ N ≤ 100)과 친구 관계의 수 M (1 ≤ M ≤ 5,000)이 주어진다. 둘째 줄부터 M개의 줄에는 친구 관계가 주어진다. 친구 관계는 A와 B로 이루어져 있으며, A와 B가 친구라는 뜻이다. A와 B가 친구이면, B와 A도 친구이며, A와 B가 같은 경우는 없다. 친구 관계는 중복되어 들어올 수도 있으며, 친구가 한 명도 없는 사람은 없다. 또, 모든 사람은 친구 관계로 연결되어져 있다. 사람의 번호는 1부터 N까지이며, 두 사람이 같은 번호를 갖는 경우는 없다.

출력

첫째 줄에 BOJ의 유저 중에서 케빈 베이컨의 수가 가장 작은 사람을 출력한다. 그런 사람이 여러 명일 경우에는 번호가 가장 작은 사람을 출력한다.

 

 

이번에는 플로이드 워셜과 너비 우선 탐색, 2가지의 경우로 풀어보았다!

 

 

플로이드 워셜

플로이드 워셜 알고리즘은 모든 노드들의 최단 경로를 구하는 알고리즘 중 하나이다.

 

알고리즘 과정은 간단하다.

처음에 NxN의 이차원 인접 행렬을 생성한다.

이후 중간자 노드를 선택하고, 임의의 두 노드에 대해 중간자 노드를 통해 이어지는지 확인한다.

위 과정을 모든 노드에 대해 중간자 노드를 선택하여 총 N round를 거치면 최단 경로 테이블이 완성된다.

 

코드로 살펴보자.

const filePath = process.platform === 'linux' ? '/dev/stdin' : 'BACKJOON_001369.txt';
const input = require('fs').readFileSync(filePath).toString().trim().split(/\r?\n/);
const [N, T] = input.shift().split(' ').map(Number);

const graph = Array.from(new Array(N), () => new Array(N).fill(10000));

input.forEach((data) => {
  const [s, e] = data.split(' ').map(Number);
  graph[s-1][e-1] = 1;
  graph[e-1][s-1] = 1;
})

for(let m=0; m<N; m++)
for(let i=0; i<N; i++)
for(let j=i+1; j<N; j++) {
  graph[i][j] = Math.min(graph[i][j], graph[i][m] + graph[m][j]);
  graph[j][i] = graph[i][j];
}

const arr = graph.map((data) => data.reduce((a, x) => a+x))
const answer = arr.reduce((iMax, x, i) => x < arr[iMax] ? i : iMax, 0) + 1;

console.log(answer)

• 5번째 줄에서 처음에 최단 경로 테이블을 초기화 해준다.
  이때, 최대 유저의 수가 100명이므로 초기값은 $ \sum\limits_{i=1}^{99} i $ 의 값인 4950보다 작으면 된다.
• 7~10번째 줄에서 주어진 입력 값에 대해 최단 경로 테이블을 갱신하였다.
  서로 친구인 사이의 경우 직접적으로 연결되어 있으므로 1로 설정해주었다.
• 13~18번째 줄에서 플로이드 워셜 알고리즘이 적용되었다.
  기존에는 j 또한 0~N까지 실행해야 하지만 이 문제에서는 graph[i][j] 와 graph[j][i]의 값이 동일하므로 j의 시작값은 i+1로 하였다.
• 20번째 줄에서 각 유저별 케빈 베이커 수를 구하고, 21번째 줄에서 케빈 베이커 수가 가장 적은 유저를 찾았다.

 

 

BFS (너비 우선 탐색)

문제에서 모든 사람은 친구 관계로 이어져있다고 하였다.
그래서 임의의 한 유저를 선택하여 연결된 친구를 BFS로 탐색하면 모든 유저를 탐색할 수 있다.

유저에 연결된 모든 유저들을 탐색하면 이제 케빈 베이커 수를 구할 수 있다.
위 과정을 모든 유저에 대해 반복하면 모든 유저에 대한 케빈 베이커 수를 구할 수 있다.

 

이번의 graph 변수는 최단 경로 테이블이 아닌 자신과 직접적으로 연결된 친구 노드를 배열로 저장하였다.
즉, graph[i]는 i 번째 노드의 직접 연결된 노드들의 배열이다.

const filePath = process.platform === 'linux' ? '/dev/stdin' : 'BACKJOON_001369.txt';
const input = require('fs').readFileSync(filePath).toString().trim().split(/\r?\n/);
const [N, T] = input.shift().split(' ').map(Number);

const graph = Array.from(new Array(N), () => []);

input.forEach((data) => {
  const [s, e] = data.split(' ').map(Number);
  graph[s-1].push(e-1);
  graph[e-1].push(s-1);
})

function bfs(i) {
  const visited = new Array(N).fill(false);
  const queue = []; let qs = 0;

  let kevin = 0;

  queue.push([i, 0]);
  visited[i] = true;

  while(qs < queue.length) {
    const [c, distance] = queue[qs]; qs++;
    kevin += distance;

    graph[c].forEach((newI) => {
      if(visited[newI]) return;

      queue.push([newI, distance + 1]);
      visited[newI] = true;
    })
  }
  return kevin;
}

const arr = Array.from({length: N}, (v, i) => bfs(i));
const answer = arr.reduce((iMax, x, i) => x < arr[iMax] ? i : iMax, 0) + 1;

console.log(answer)

 

 

회고

어제 플로이드 워셜 알고리즘를 사용하여 푸는 문제가 나왔었다. 어제 풀어본 문제와 비슷하여서 오늘은 빠른 시간 내에 푼 것 같다.
어제와 오늘 나왔던 문제 둘 다 이전에 풀어본 적이 있는 문제였다. 이전에는 C++로 풀었지만 이제 JavaScript로 풀면서 두 언어의 차이를 알게되는 것 같다.
C++로 풀때는 기본적은 자료구조는 라이브러리로 만들어져있어서 바로 사용할 수 있지만 JavaScript는 array 외의 stack, queue, priority_queue 가 제공되지 않는다.. 그래서 적절히 array를 수정하여서 사용하거나 직접 class 를 만들어야 한다.

하지만 js에서는 map, forEach, reduce, filter와 같은 고차함수가 매서드로 제공된다. 이를 활용해 더욱 간단한 코드를 작성할 수 있는 것 같다!