C++로 해결하는 페인트 하우스 II: 최소 비용으로 집 색칠하기

문제 개요

n개의 집이 한 줄로 나열되어 있고, 각 집은 k가지 색상 중 하나로 칠할 수 있다고 가정해 봅시다. 집마다 특정 색상으로 칠하는 비용은 서로 다릅니다. 이때 인접한 두 집이 같은 색이 되지 않도록 모든 집을 칠해야 한다는 조건이 있습니다.

각 집을 특정 색으로 칠하는 비용은 n × k 크기의 행렬로 주어지며, 우리의 목표는 모든 집을 칠하는 데 드는 최소 비용을 구하는 것입니다.

예시

입력이 다음과 같다고 가정해 보겠습니다.

1	5	3
2	9	4

이 경우 출력은 5입니다. 0번 집을 0번 색으로, 1번 집을 2번 색으로 칠하면 비용은 1 + 4 = 5가 됩니다. 마찬가지로 0번 집을 2번 색으로, 1번 집을 0번 색으로 칠해도 3 + 2 = 5로 동일한 최소 비용을 얻을 수 있습니다.

해결 접근 방식

이 문제는 동적 계획법(Dynamic Programming)으로 효율적으로 해결할 수 있습니다. 핵심 아이디어는 각 집을 칠할 때, 현재 선택한 색을 제외한 이전 집 행의 최소 비용을 빠르게 찾는 것입니다. 이를 위해 왼쪽 방향 누적 최솟값 배열(lmins)과 오른쪽 방향 누적 최솟값 배열(rmins), 두 개의 보조 배열을 활용합니다.

구체적인 알고리즘 단계는 다음과 같습니다.

n := costs의 행(row) 크기
m := n이 0이 아니면 costs의 열(column) 크기, 그렇지 않으면 0
ret := 무한대(inf)
i := 1부터 n 미만까지 반복:
- req := 무한대
- 크기 m의 배열 lmins, rmins 선언
- lmins[0] := costs[i-1][0], rmins[m-1] := costs[i-1][m-1]
- j := 1부터 m 미만까지: lmins[j] := min(costs[i-1][j], lmins[j-1]) — 왼쪽→오른쪽 누적 최솟값 계산
- j := m-2부터 0 이상까지 역순: rmins[j] := min(costs[i-1][j], rmins[j+1]) — 오른쪽→왼쪽 누적 최솟값 계산
- j := 0부터 m 미만까지:
  - left := (j-1 ≥ 0이면 lmins[j-1], 아니면 무한대)
  - right := (j+1 < m이면 rmins[j+1], 아니면 무한대)
  - costs[i][j] := costs[i][j] + min(left, right)
i := 0부터 m 미만까지: ret := min(ret, costs[n-1][i]) — 마지막 행에서 최솟값 추출
ret이 여전히 무한대라면 0을 반환하고, 그렇지 않으면 ret을 반환

이 방식을 사용하면 각 집·색 조합에 대해 이전 행의 최솟값을 O(1) 시간에 구할 수 있어 전체 시간 복잡도가 O(n × k)가 됩니다. 매번 이전 행 전체를 탐색하는 단순한 O(n × k²) 방식보다 훨씬 효율적이라는 점이 이 알고리즘의 가장 큰 장점입니다.

C++ 구현 예제

아래 코드를 통해 더 자세히 이해해 보겠습니다.

#include <bits/stdc++.h>
using namespace std;
class Solution {
public:
   int minCostII(vector<vector<int>>& costs) {
      int n = costs.size();
      int m = n ? costs[0].size() : 0;
      int ret = INT_MAX;
      for (int i = 1; i < n; i++) {
         int req = INT_MAX;
         vector<int> lmins(m);
         vector<int> rmins(m);
         lmins[0] = costs[i - 1][0];
         rmins[m - 1] = costs[i - 1][m - 1];
         for (int j = 1; j < m; j++) {
            lmins[j] = min(costs[i - 1][j], lmins[j - 1]);
         }
         for (int j = m - 2; j >= 0; j--) {
            rmins[j] = min(costs[i - 1][j], rmins[j + 1]);
         }
         for (int j = 0; j < m; j++) {
            int left = j - 1 >= 0 ? lmins[j - 1] : INT_MAX;
            int right = j + 1 < m ? rmins[j + 1] : INT_MAX;
            costs[i][j] += min(left, right);
         }
      }
      for (int i = 0; i < m; i++) {
         ret = min(ret, costs[n - 1][i]);
      }
      return ret == INT_MAX ? 0 : ret;
   }
};
main(){
   Solution ob;
   vector<vector<int>> v = {{1,5,3},{2,9,4}};
   cout <<(ob.minCostII(v));
}

입력

{{1,5,3},{2,9,4}}