[알고리즘 연습] 백준 21278 (호석이 두 마리 치킨, 자바스크립트)

문제

21278번: 호석이 두 마리 치킨

---

풀이

• 플로이드 와샬 알고리즘을 통해 모든 노드간 최단 거리를 구한다.
• 2곳에 치킨집이 존재할 수 있는 케이스를 모두 탐색해 최단 시간의 총합을 구한다.

소스 코드

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

const [N, M] = input[0].split(" ").map((el) => +el);
const arr = Array.from({ length: N + 1 }, () => Array(N + 1).fill(0));
let min = Infinity;
let answer;

for (let i = 1; i <= N; i++) {
  for (let j = 1; j <= N; j++) {
    if (i === j) continue;
    arr[i][j] = Infinity;
  }
}

for (let i = 1; i <= M; i++) {
  const [a, b] = input[i].split(" ").map((el) => +el);

  arr[a][b] = 1;
  arr[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 (arr[i][j] > arr[i][k] + arr[k][j]) {
        arr[i][j] = arr[i][k] + arr[k][j];
      }
    }
  }
}

// 치킨집 위치 : (i, j)
for (let i = 1; i < N; i++) {
  for (let j = i + 1; j <= N; j++) {
    let sum = 0;

    // 플로이드 와샬 알고리즘을 통해 이미 최단 거리를 구했다.
    for (let k = 1; k <= N; k++) {
      sum += Math.min(arr[k][i] * 2, arr[k][j] * 2);
    }

    if (min > sum) {
      min = sum;
      answer = [i, j];
    }
  }
}

console.log(answer[0] + " " + answer[1] + " " + min);