문제 개요

문제: 서강그라운드

분류: 그래프 이론, 다익스트라, 최단 경로, 플로이드-워셜

난이도: 골드4

문제 풀이

플로이드 와샬 알고리즘으로 최단 거리 테이블을 만들고 이를 행별로 탐색하며 어떤 지역까지의 거리가 m보다 작거나 같은 경우에만 아이템 개수를 세아린다.

세아린 아이템 개수가 정답 변수보다 큰 경우, 정답 변수를 업데이트 한다.

코드

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

const [n, m, r] = nmr.split(" ").map(Number);
items = items.split(" ").map(Number);

const solution = (n, m, r, items, roadInfo) => {
  let answer = 0;
  const dist = Array.from({ length: n + 1 }, () =>
    new Array(n + 1).fill(Infinity)
  );

  roadInfo.forEach((road) => {
    const [from, to, d] = road.split(" ").map(Number);
    dist[from][to] = d;
    dist[to][from] = d;
  });

  for (let k = 1; k <= n; k++) {
    for (let i = 1; i <= n; i++) {
      for (let j = 1; j <= n; j++) {
        if (i === j) dist[i][j] = 0;
        if (dist[i][j] > dist[i][k] + dist[k][j])
          dist[i][j] = dist[i][k] + dist[k][j];
      }
    }
  }

  for (let i = 1; i <= n; i++) {
    let itemCnt = 0;
    for (let j = 1; j <= n; j++) {
      if (dist[i][j] <= m) itemCnt += items[j - 1];
    }
    answer = Math.max(answer, itemCnt);
  }

  console.log(answer);
};

solution(n, m, r, items, roadInfo);