[Baekjoon] 1149.RGB거리 (node.js)

일흔 세 번째 포스팅

안녕하세요! 일흔 세 번째 포스팅으로 찾아뵙게 되어 반갑습니다!♥

오늘의 포스팅 내용은 백준 - RGB거리에 관한 내용입니다.
자세한 내용을 알아보러 갑시다❗️

[Boongranii] Here We Go 🔥

---

1️⃣ 문제

[백준] RGB거리 (문제 링크)

💨 문제 설명

RGB거리에는 집이 N개 있다. 거리는 선분으로 나타낼 수 있고, 1번 집부터 N번 집이 순서대로 있다.

집은 빨강, 초록, 파랑 중 하나의 색으로 칠해야 한다. 각각의 집을 빨강, 초록, 파랑으로 칠하는 비용이 주어졌을 때, 아래 규칙을 만족하면서 모든 집을 칠하는 비용의 최솟값을 구해보자.

• 1번 집의 색은 2번 집의 색과 같지 않아야 한다.
• N번 집의 색은 N-1번 집의 색과 같지 않아야 한다.
• i(2 ≤ i ≤ N-1)번 집의 색은 i-1번, i+1번 집의 색과 같지 않아야 한다.

💨 입력

첫째 줄에 집의 수 N(2 ≤ N ≤ 1,000)이 주어진다. 둘째 줄부터 N개의 줄에는 각 집을 빨강, 초록, 파랑으로 칠하는 비용이 1번 집부터 한 줄에 하나씩 주어진다. 집을 칠하는 비용은 1,000보다 작거나 같은 자연수이다.

💨 출력

첫째 줄에 모든 집을 칠하는 비용의 최솟값을 출력한다.

💨 입출력 예

※ 참고로 변수 설정 및 입력값 설정은 해결 방법에 따라 달라질 수 있음. 아래와 같이 배열 및 변수명은 본인이 커스텀한 것임.

N	arr	return
3	[[26 40 83], [49 60 57], [13 89 99]]	96
3	[[1 100 100], [100 1 100], [100 100 1]]	3
3	[[1 100 100], [100 100 100], [1 100 100]]	102
6	[[30 19 5], [64 77 64], [15 19 97], [4 71 57], [90 86 84], [93 32 91]]	208
8	[[71 39 44], [32 83 55], [51 37 63], [89 29 100], [83 58 11], [65 13 15], [47 25 29], [60 66 19]]	253

💨 알고리즘 분류

• 다이나믹 프로그래밍

---

2️⃣ 문제 풀이

🔥 나의 문제 풀이

1. 동적계획법을 사용하여 문제 해결
2. 총 3개의 색깔이므로 3개의 열로 이루어진 dp 배열을 만듦.
3. 초기값을 설정해줌.
4. 이전 집의 색깔과 다른 색깔을 칠하는 비용을 더해줌.
5. 반복문이 끝난 후 계산된 dp 배열의 마지막 행에서 가장 작은 값을 찾아 출력함.

const fs = require("fs");
const filePath = process.platform === "linux" ? "/dev/stdin" : "example.txt";
const [N, ...arr] = fs.readFileSync(filePath).toString().trim().split("\n");

const dp = Array.from({ length: N }, () => Array(3).fill(0));
let answer = 0;

for (let i = 0; i < N; i++) {
  arr[i] = arr[i].split(" ").map(Number);
}

dp[0][0] = arr[0][0];
dp[0][1] = arr[0][1];
dp[0][2] = arr[0][2];

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

answer = Math.min(dp[N - 1][0], dp[N - 1][1], dp[N - 1][2]);
console.log(answer);

주어진 문제를 이해하는 데 조금 걸린 것 같다. 프로그래머스처럼 조금 더 친절한 설명이 있으면 좋겠다…

주어진 문제는 동적계획법으로 해결하는 문제이다. 각 집을 색칠하는 비용이 주어질 때, 인접한 두 집이 같은 색이 아니도록 하면서 모든 집을 색칠하는 최소 비용을 구하는 것이다.

dp[i][j]는 i번재 집을 j번째 색으로 칠할 때의 최소 비용을 나타낸다. j는 0(빨강), 1(초록), 2(파랑)을 의미한다.

첫 번째 집의 경우, 선택 가능한 색의 비용이 그대로 초기 값이 된다. dp[0][0] = arr[0][0], dp[0][1] = arr[0][1], dp[0][2] = arr[0][2] 이다.

이제 점화식을 정의하면 된다. 각 집에 대해 선택 가능한 색의 최소 비용을 계산하면 된다. 현재 집을 특정 색으로 칠할 경우, 이전 집에서 선택할 수 있는 다른 두 색의 최소 비용을 더해주면 된다.

dp[i][0] = Math.min(dp[i - 1][1], dp[i - 1][2]) + arr[i][0];
dp[i][1] = Math.min(dp[i - 1][0], dp[i - 1][2]) + arr[i][1];
dp[i][2] = Math.min(dp[i - 1][0], dp[i - 1][1]) + arr[i][2];

마지막으로 마지막 집의 색깔 선택에서의 최소 비용이 전체의 최소 비용이 되는 것이다.

---

3️⃣ 느낀점

프로그래머스에서 이와 비슷한 문제를 풀었던 기억이 나는 것 같기도 하다. 문제를 이해하고 동적계획법으로 해결 해야겠다고 생각했다.

바텀업(bottom-up) 방식을 통해 해결해였으며, 작은 문제는 첫 번째 집을 색칠하는 비용을 계산하는 것이며, 이후 반복문을 통해 각 집을 색칠하는 최소 비용을 차례대로 계산한다.

이상털😌💫