백준 / 그래프 / 11404번 / 플로이드 / JS

문제 간단설명

n(2 ≤ n ≤ 100)개의 도시가 있다. 그리고 한 도시에서 출발하여 다른 도시에 도착하는 m(1 ≤ m ≤ 100,000)개의 버스가 있다. 각 버스는 한 번 사용할 때 필요한 비용이 있다.

모든 도시의 쌍 (A, B)에 대해서 도시 A에서 B로 가는데 필요한 비용의 최솟값을 구하는 프로그램을 작성하시오.

 

제한 사항

• 2 <= n <= 100
• 1 <= m <= 100,000
• 1 <= c <= 100,000
• 시작 도시와 도착 도시를 연결하는 노선은 하나가 아닐 수 있다.

 

성공 코드

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

const n = +input.shift();
const m = +input.shift();
const busList = input.map((row) => row.split(' ').map(Number));

const solution = () => {
  const adjMatrix = Array.from({ length: n + 1 }, () =>
    Array.from({ length: n + 1 }, () => Infinity)
  );

  /**
   * 인접행렬을 만드는 함수이다.
   */
  const initAdjMatrix = () => {
    for (const [start, end, cost] of busList) {
      adjMatrix[start][end] = Math.min(adjMatrix[start][end], cost);
    }

    for (let i = 1; i <= n; i++) {
      for (let j = 1; j <= n; j++) {
        // 자기자신으로 가는 비용은 0으로 초기화해준다.
        if (i === j) {
          adjMatrix[i][j] = 0;
        }
      }
    }
  };

  /**
   * Floyd-Warshall 알고리즘으로 최단거리를 구하는 함수이다.
   */
  const floydWarshall = () => {
    for (let k = 1; k <= n; k++) {
      for (let i = 1; i <= n; i++) {
        for (let j = 1; j <= n; j++) {
          if (adjMatrix[i][j] > adjMatrix[i][k] + adjMatrix[k][j]) {
            adjMatrix[i][j] = adjMatrix[i][k] + adjMatrix[k][j];
          }
        }
      }
    }
  };

  /**
   * 정답을 주어진 형식에 맞게 출력하는 함수이다.
   */
  const printResult = () => {
    for (let i = 1; i <= n; i++) {
      const row = [];
      for (let j = 1; j <= n; j++) {
        if (adjMatrix[i][j] === Infinity) {
          row.push(0);
        } else {
          row.push(adjMatrix[i][j]);
        }
      }

      console.log(row.join(' '));
    }
  };

  initAdjMatrix();
  floydWarshall();
  printResult();
};

solution();