[백준 2660] 회장뽑기 with node.js

📌 문제

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

📌 풀이

• graphOfFriendship에서 친구 관계를 모두 이어서 표현해준다.
• BFS로 1번부터 마지막 회원의 수(numOfMember)까지 연결되어 있는 거리를 누적으로 더해주면서 가장 긴 거리를 pointOfCandidate(후보의 점수)로 가져온다.
• pointOfChairman 갱신하고 candidateOfChairman를 다시 초기화 해주면서 회장이 될수 잇는 사람을 찾으면 된다.

📌 코드

const fs = require('fs');
const stdin = (
  process.platform === 'linux'
    ? fs.readFileSync('/dev/stdin').toString().trim()
    : `5
1 2
2 3
3 4
4 5
2 4
5 3
-1 -1`
).split('\n');

const input = (() => {
  let line = 0;
  return () => stdin[line++];
})();

const getMaxDistance = (startVertex) => {
  const distance = new Array(numOfMember + 1).fill(0);
  const visitedVertices = new Array(numOfMember + 1).fill(false);
  let queue = [startVertex];
  let queueCursor = 0;
  visitedVertices[startVertex] = true;

  while (queue.length > queueCursor) {
    const vertex = queue[queueCursor++];
    for (let nextVertex of graphOfFriendship[vertex]) {
      if (visitedVertices[nextVertex]) continue;

      visitedVertices[nextVertex] = true;
      queue.push(nextVertex);
      distance[nextVertex] = distance[vertex] + 1;
    }
  }

  return Math.max.apply(null, distance);
};

const numOfMember = parseInt(input());
const graphOfFriendship = Array.from(Array(numOfMember + 1), () => new Array());
while (1) {
  const [vertexA, vertexB] = input().split(' ').map(Number);
  if (vertexA === -1 && vertexB === -1) break;

  graphOfFriendship[vertexA].push(vertexB);
  graphOfFriendship[vertexB].push(vertexA);
}

let candidateOfChairman = [];
let pointOfChairman = 51;
for (let i = 1; i <= numOfMember; i++) {
  let pointOfCandidate = getMaxDistance(i);
  if (pointOfCandidate === pointOfChairman) {
    candidateOfChairman.push(i);
  } else if (pointOfCandidate < pointOfChairman) {
    candidateOfChairman = [i];
    pointOfChairman = pointOfCandidate;
  }
}

console.log(pointOfChairman, candidateOfChairman.length);
console.log(...candidateOfChairman);