[백준] 1389 - 케빈 베이컨의 6단계 법칙 (Javascript / node)

문제

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

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

풀이

const fs = require("fs");
const filePath = process.platform === "linux" ? "/dev/stdin" : "./input.txt";
let input = fs.readFileSync(filePath).toString().trim().split("\n");

class Queue {
  constructor() {
    this.items = {};
    this.headIndex = 0;
    this.tailIndex = 0;
  }
  enqueue(item) {
    this.items[this.tailIndex] = item;
    this.tailIndex++;
  }
  dequeue(){
    const item = this.items[this.headIndex];
    delete this.items[this.headIndex];
    this.headIndex++;
    return item;
  }
  peek(){
		return this.items[this.headIndex]
	}
	getLength(){
		return this.tailIndex - this.headIndex;
	} 
}
// N: 유저의 수 , M: 친구 관계의 수
const [N, M] = input[0].split(" ").map(Number);

const graph = Array.from({length: N+1}, () => []);
for(let i = 1; i<=M; i++){
  const[A, B] = input[i].split(" ").map(Number);
  graph[A].push(B)
  graph[B].push(A)
}

const bfs = (start) => {
  const queue = new Queue();
  const visited = Array(N+1).fill(0);
  queue.enqueue([start,0]);
  while(queue.getLength()){
    const [current, distance] = queue.dequeue();
    for(const B of graph[current]){
      if(!visited[B]){
        visited[B] = distance+1;
        queue.enqueue([B, distance+1]);
      } 
    }
  }
  return visited.reduce((acc, curr) => acc+curr);
}
let minScore = Number.MAX_VALUE;
let answer = -1;
for(let i = 1; i <= N; i++){
  const score = bfs(i);
  if (score < minScore) {
    minScore = score;
    answer = i;
  }
}

console.log(answer);

 

1. bfs를 구현하기 위해 class Queue를 만든다.

2. 친구(정선)간의 관계(간선)을 graph에 저장

3. bfs내 중복제거를 위해 visited를 만든다. 친구의 단계를 나타내기 위해 distance를 친구정보와 같이 queue에 넣어준다.

4. visited에 친구단계(distance)를 넣어줬기에 합산한 결과를 return한다. 

5. 최소점수를 찾기에 기존 최소점수보다 낮지 않다면 minScore에 할당하지 않는다.

6. 마지막 answer이 최소점수를 가진 유저가 된다.