[JavaScript/DP] 백준 실버 1 : 4883 - 삼각 그래프

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

4883번: 삼각 그래프

---

📌 작성한 코드 

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

const answer = [];

let idx = 0;
while (true) {
    const N = Number(input[idx]);
    if (N === 0) break;

    const list = [];
    for (let i = idx + 1; i <= idx + N; i++) {
        list.push(input[i].split(" ").map(Number));
    }
    idx += N + 1;

    const dp = Array.from({ length: N }, () => new Array(3));
    dp[0][0] = list[0][0];
    dp[0][1] = list[0][1];
    dp[0][2] = list[0][2] + list[0][1];

    dp[1][0] = list[0][1] + list[1][0];
    dp[1][1] = Math.min(dp[0][1], dp[0][2], dp[1][0]) + list[1][1];
    dp[1][2] = Math.min(dp[0][1], dp[0][2], dp[1][1]) + list[1][2];

    for (let i = 2; i < N; i++) {
        dp[i][0] = Math.min(dp[i - 1][0], dp[i - 1][1]) + list[i][0];
        dp[i][1] = Math.min(dp[i - 1][0], dp[i - 1][1], dp[i - 1][2], dp[i][0]) + list[i][1];
        dp[i][2] = Math.min(dp[i - 1][1], dp[i - 1][2], dp[i][1]) + list[i][2];
    }

    answer.push(dp[N - 1][1]);
}

console.log(answer.map((v, i) => `${i + 1}. ${v}`).join("\n"));

 

📌 설명 

dp를 이용해서 각 단계마다 최소 비용을 저장하며 도착지의 최소 비용을 구하는 문제이다. 

 

- 점화식 구하기, 초기값 세팅하기

해당 문제는 각 정점의 열의 위치에 따라서 도달할 수 있는 경로가 정해져 있기 때문에, 현재 정점에 도달 할 수 있는 경로를 살펴보고 해당 경로 중 최소 비용을 가진 경로에 현재 정점의 비용을 더한 값을 더해주면 된다. 하지만 이 때 주의해야 할 부분이 있는데 첫번째는 맨 위의 가운데 위치([0][1])에서 시작한다는 것이고, 두번째는 정점의 비용이 음수일 수 있다는 것이다. 

 

그래서 dp의 초기값을 지정해 줄 때 주의해야 한다. 

- [0][0]이 포함된 루트는 [0][1]에서 시작할 수 없으므로 해당 루트는 계산하지 않는다.

- [0][2]가 포함된 루트는 [0][1]에서 시작하는 루트 밖에 없다. ([0][2]에서 시작 불가능)

 

- [1][0]에 도달하는 루트는 [0][1]에서 시작하는 루트 밖에 없다. ([0][0]에서 시작 불가능)

- [1][1]에 도달하는 루트는 [0][0]에서 시작하는 루트를 제외한 루트이다. ([0][0]에서 시작 불가능)

 

굳이 이렇게 모든 루트를 확인해주는 이유는 간선 중에 음수가 있을 수 있기 때문이다. 값이 양수밖에 없다면 더할 수록 더 큰 값이 되니까 아래로 바로 내려가는 루트를 선택하는 것이 합리적이겠지만, 음수가 존재하는 순간 음수를 지나는 것이 더 적은 비용이 들기 때문에 모든 루트를 확인해서 음수를 지나갈 수 있게 해준다. 

 

이렇게 초기값을 정해준 다음에 i=2부터는 정상적으로 모든 루트를 고려하면서 최소 비용을 구해나가면 된다. 

 

const dp = Array.from({ length: N }, () => new Array(3));
    dp[0][0] = list[0][0]; // 실제로 사용되지 않음
    dp[0][1] = list[0][1];
    dp[0][2] = list[0][2] + list[0][1]; // 무조건 0,0 지난 루트만 가능

    dp[1][0] = list[0][1] + list[1][0]; // 0,1에서 시작하는 루트만 가능
    dp[1][1] = Math.min(dp[0][1], dp[0][2], dp[1][0]) + list[1][1]; // 0,0에서 시작하는 루트 제외
    dp[1][2] = Math.min(dp[0][1], dp[0][2], dp[1][1]) + list[1][2];

    for (let i = 2; i < N; i++) {
        dp[i][0] = Math.min(dp[i - 1][0], dp[i - 1][1]) + list[i][0];
        dp[i][1] = Math.min(dp[i - 1][0], dp[i - 1][1], dp[i - 1][2], dp[i][0]) + list[i][1];
        dp[i][2] = Math.min(dp[i - 1][1], dp[i - 1][2], dp[i][1]) + list[i][2];
    }

 

 

✅ 성공