문제 개요

문제: 회장뽑기

분류: 그래프 이론, 그래프 탐색, 너비 우선 탐색, 최단 경로, 플로이드-워셜

난이도: 골드5

문제 풀이

플로이드 와샬 알고리즘을 사용하여 풀이했다.

서로 친구인 a, b에 대해 최단 거리 테이블에서 dist[a][b]와 dist[b][a]를 1로 초기화한다.

이후 플로이드 와샬 알고리즘을 적용하는데 이때 어떤 회원이 다른 모든 회원과 친구라면 그 회원에 해당하는 행에는 전부 1이 저장된다.
만약 다른 모든 회원과 친구이거나 친구의 친구이면 친구의 친구에 해당하는 사람의 칸에는 2가 저장되어 있을 것이다. a→b가 아니라 a→c→b의 거리가 저장되어 있기 때문이다.

최단 거리 테이블을 행별로 탐색하며 각 행마다 가장 큰 수를 score 배열에 저장한다. 즉, score[i]는 i번째 회원의 점수가 된다.
그리고 score 배열에 저장된 값 중 가장 작은 값 minScore가 회장 후보의 점수가 된다.

마지막으로 score 배열을 탐색하며 minScore와 같은 값을 가지는 사람의 번호를 변수에 저장하고, 문제에서 요구하는 값들을 출력하면 정답이 된다.

코드

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

const solution = () => {
  const N = +input.shift();
  const friends = input
    .slice(0, input.length - 1)
    .map((v) => v.split(" ").map(Number));
  const dist = Array.from(Array(N + 1), () => Array(N + 1).fill(Infinity));

  friends.forEach(([a, b]) => {
    dist[a][b] = 1;
    dist[b][a] = 1;
  });

  for (let k = 1; k <= N; k++) {
    for (let i = 1; i <= N; i++) {
      for (let j = 1; j <= N; j++) {
        if (i === j) continue;
        dist[i][j] = Math.min(dist[i][j], dist[i][k] + dist[k][j]);
      }
    }
  }

  const score = new Array(N + 1).fill(0);
  let minScore = Infinity;
  for (let i = 1; i <= N; i++) {
    for (let j = 1; j <= N; j++) {
      if (i === j) continue;
      score[i] = Math.max(score[i], dist[i][j]);
    }
    minScore = Math.min(minScore, score[i]);
  }

  const answerArr = [];
  for (let i = 1; i <= N; i++) {
    if (minScore === score[i]) answerArr.push(i);
  }

  console.log(minScore, answerArr.length);
  console.log(answerArr.join(" "));
};

solution();