백준 [node.js] > 1916번 최소 비용 구하기

 

문제

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

 

풀이

처음에 dfs로 접근해서 풀었는데 시간초과로 틀려서 dp를 이용했다.

 

일단 map이라는 2차원 배열을 구현한다. 이 2차원 배열의 map[ i ][ j ] 는 i도시에서 j 도시로 갈 시 가장 가격이 싼 버스 요금을 나타 낸다. 만약 map[ i ][ j ] = Infinity 이면 해당 루트는 버스가 다니지 않는다고 생각하면 된다. 

 

그리고 dp라는 2차원 배열을 구현한다. 

dp[ i ][ j ] 는 i 도시에서 j 도시로 가는 루트는 가장 버스요금이 싼 루트의 요금을 나타낸다.

우리는 모든 경로를 탐색하면서 2차원 배열 dp를 완성시키고 최종적으로 dp[출발점][도착점] => 최소비용 을 구하면 된다. 

 

const fs = require("fs");
const input = fs.readFileSync("/dev/stdin").toString().trim().split("\n");

let [cityCnt, routeCnt, ...arr] = input;

cityCnt = Number(cityCnt);
routeCnt = Number(routeCnt);

let [start, end] = arr
    .pop()
    .split(" ")
    .map((num) => Number(num));

// 2차원 배열 생성 ( 요금 표시를 위해 )
// map[i][j] => i포인트에서 j포인트로 가는 루트의 요금
let map = Array.from({ length: cityCnt + 1 }, () => {
    return Array(cityCnt + 1).fill(Infinity);
});

for (let i = 0; i < arr.length; ++i) {
    let [s, e, pay] = arr[i].split(" ").map((num) => Number(num));
    if (map[s][e] !== Infinity) {
        map[s][e] = Math.min(pay, map[s][e]);
    } else {
        map[s][e] = pay;
    }
}

let dp = Array.from({ length: cityCnt + 1 }, () => {
    return Array(cityCnt + 1).fill(Infinity);
});

let rest = [];

for (let i = 1; i < cityCnt + 1; ++i) {
    if (map[start][i] !== Infinity) {
        dp[start][i] = map[start][i];
        rest.push(i);
    }
}
while (rest.length) {
    let middlePoint = rest.shift();
    for (let i = 1; i < cityCnt + 1; ++i) {
        if (map[middlePoint][i] !== Infinity && dp[start][middlePoint] !== Infinity) {
            if (dp[start][i] > dp[start][middlePoint] + map[middlePoint][i]) {
                dp[start][i] = dp[start][middlePoint] + map[middlePoint][i];

                if (!rest.includes(i)) {
                    rest.push(i);
                }
            }
        }
    }
}

console.log(dp[start][end]);