여러 채의 집이 일렬로 있습니다.

각 집은 여러 색 중 하나로 칠할 수 있고, 색마다 칠하는 비용이 다릅니다. 단, 바로 옆에 있는 두 집은 같은 색으로 칠할 수 없습니다.

이번 글에서는 각 집을 각 색으로 칠하는 비용이 2차원 배열로 주어질 때, 조건을 만족하면서 전체 비용을 최소로 만드는 방법을 Java DP로 정리합니다.

문제

집이 N채 있고, 사용할 수 있는 색이 K개 있습니다.

costs[i][j]는 i번 집을 j번 색으로 칠하는 비용입니다. 바로 옆에 있는 두 집은 같은 색으로 칠할 수 없습니다.

이 조건을 지키면서 모든 집을 칠하는 최소 비용을 구해야 합니다.

입력 예시

int[][] costs = {
        {8, 16, 12},
        {14, 5, 13},
        {19, 18, 7}
};

이 배열은 다음처럼 볼 수 있습니다.

집0번 색1번 색2번 색
0번 집81612
1번 집14513
2번 집19187

예를 들어 costs[1][0]은 1번 집을 0번 색으로 칠하는 비용입니다.

costs[1][0] = 14;

출력 예시

20

왜 정답이 20일까?

가장 싼 선택 중 하나는 다음과 같습니다.

집선택한 색비용
0번 집0번 색8
1번 집1번 색5
2번 집2번 색7

총 비용은 다음과 같습니다.

8 + 5 + 7 = 20

색의 흐름은 다음과 같습니다.

0번 색 -> 1번 색 -> 2번 색

옆집끼리 색이 같지 않으므로 조건을 만족합니다. 따라서 이 예시의 최소 비용은 20입니다.

처음 떠오르는 생각

각 집에서 가장 싼 색만 고르면 될 것처럼 보일 수 있습니다.

하지만 바로 이전 집과 색이 같아지면 그 선택은 사용할 수 없습니다. 현재 집의 선택은 바로 이전 집의 선택에 영향을 받습니다.

그래서 이 문제는 이전 집까지의 최소 비용을 저장해두고 다음 집 계산에 활용하는 DP로 풀기 좋습니다.

핵심 아이디어

dp[house][color]를 다음처럼 정의합니다.

dp[house][color]
= house번 집을 color번 색으로 칠했을 때,
  그 집까지 칠하는 데 필요한 최소 누적 비용

예를 들어 dp[1][0]은 다음 뜻입니다.

1번 집을 0번 색으로 칠했을 때,
0번 집부터 1번 집까지의 최소 비용

현재 집을 color번 색으로 칠한다면, 바로 이전 집은 color번 색이면 안 됩니다.

따라서 이전 집에서 현재 색과 다른 색만 확인하고, 그중 가장 싼 값을 현재 비용에 더합니다.

dp[house][color]
= costs[house][color] + min(dp[house - 1][다른 색])

Interactive DP

집 색칠 최소 비용 DP 애니메이션

버튼을 눌러서 costs에서 dp가 채워지는 흐름을 한 단계씩 볼 수 있습니다.

시작합니다. costs는 원래 비용표이고, dp에는 최소 누적 비용을 채웁니다.

현재 계산이전 집 후보같은 색이라 제외저장된 결과

비용표 costs

집0번 색1번 색2번 색
0번 집81612
1번 집14513
2번 집19187

각 칸 = 해당 집을 해당 색으로 칠하는 비용

누적 최소 비용표 dp

집0번 색1번 색2번 색
0번 집
1번 집
2번 집

각 칸 = 여기까지 칠했을 때의 최소 누적 비용

핵심 생각

현재 집을 color 색으로 칠한다.
-> 이전 집은 color 색이면 안 된다.
-> 이전 집의 다른 색들 중 가장 싼 값을 고른다.
-> 현재 비용과 더해서 dp에 저장한다.

코드

public class PaintHouseK {

    public static int minCost(int[][] costs) {
        if (costs == null || costs.length == 0) {
            return 0;
        }

        int n = costs.length;
        int k = costs[0].length;

        if (k == 0) {
            return 0;
        }

        if (k == 1 && n > 1) {
            return -1;
        }

        int[][] dp = new int[n][k];

        for (int color = 0; color < k; color++) {
            dp[0][color] = costs[0][color];
        }

        for (int house = 1; house < n; house++) {
            for (int color = 0; color < k; color++) {
                int minPrevCost = Integer.MAX_VALUE;

                for (int prevColor = 0; prevColor < k; prevColor++) {
                    if (prevColor == color) {
                        continue;
                    }

                    if (dp[house - 1][prevColor] < minPrevCost) {
                        minPrevCost = dp[house - 1][prevColor];
                    }
                }

                dp[house][color] = costs[house][color] + minPrevCost;
            }
        }

        int answer = Integer.MAX_VALUE;

        for (int color = 0; color < k; color++) {
            if (dp[n - 1][color] < answer) {
                answer = dp[n - 1][color];
            }
        }

        return answer;
    }

    public static void main(String[] args) {
        int[][] costs = {
                {8, 16, 12},
                {14, 5, 13},
                {19, 18, 7}
        };

        System.out.println(minCost(costs));
    }
}

코드 해설

빈 입력 처리

if (costs == null || costs.length == 0) {
    return 0;
}

칠할 집이 없으면 비용도 없습니다. 그래서 0을 반환합니다.

집 개수와 색 개수 구하기

int n = costs.length;
int k = costs[0].length;

n은 집 개수입니다. k는 색 개수입니다.

예시에서는 집이 3채이고 색이 3개입니다.

n = 3
k = 3

첫 번째 집 처리

첫 번째 집은 이전 집이 없습니다. 그래서 각 색의 비용을 그대로 dp에 넣습니다.

for (int color = 0; color < k; color++) {
    dp[0][color] = costs[0][color];
}

결과는 다음과 같습니다.

dp[0] = [8, 16, 12]

두 번째 집부터 계산

두 번째 집부터는 바로 이전 집의 색과 겹치면 안 됩니다.

핵심 코드는 이 부분입니다.

if (prevColor == color) {
    continue;
}

현재 색과 이전 색이 같으면 건너뜁니다.

예를 들어 현재 집을 0번 색으로 칠한다면, 이전 집의 0번 색은 제외합니다.

현재 집 색: 0번 색
이전 집에서 확인할 색: 1번 색, 2번 색

가능한 이전 비용 중 가장 싼 값을 찾습니다.

if (dp[house - 1][prevColor] < minPrevCost) {
    minPrevCost = dp[house - 1][prevColor];
}

마지막으로 현재 집 비용과 이전 최소 비용을 더해서 저장합니다.

dp[house][color] = costs[house][color] + minPrevCost;

동작 방식

1번 집을 0번 색으로 칠하는 경우를 보겠습니다.

현재 비용은 다음과 같습니다.

costs[1][0] = 14;

이전 집인 0번 집에서는 0번 색을 고르면 안 됩니다. 그래서 이전 집의 1번 색과 2번 색만 비교합니다.

dp[0][1] = 16
dp[0][2] = 12

둘 중 더 싼 값은 12입니다. 따라서 계산은 다음과 같습니다.

14 + 12 = 26

그래서 다음 값이 저장됩니다.

dp[1][0] = 26;

이 값은 최종 정답이 아닙니다. 뜻은 다음과 같습니다.

1번 집을 0번 색으로 칠했을 때,
0번 집부터 1번 집까지의 최소 비용은 26이다.

실행 예시

예시 입력을 계산하면 dp는 다음 흐름으로 채워집니다.

첫 번째 집은 비용 그대로입니다.

dp[0] = [8, 16, 12]

두 번째 집을 계산합니다.

dp[1][0] = 14 + min(16, 12) = 26
dp[1][1] = 5 + min(8, 12) = 13
dp[1][2] = 13 + min(8, 16) = 21

따라서 두 번째 줄은 다음과 같습니다.

dp[1] = [26, 13, 21]

세 번째 집을 계산합니다.

dp[2][0] = 19 + min(13, 21) = 32
dp[2][1] = 18 + min(26, 21) = 39
dp[2][2] = 7 + min(26, 13) = 20

따라서 마지막 줄은 다음과 같습니다.

dp[2] = [32, 39, 20]

마지막 집까지 계산한 결과 중 가장 작은 값이 정답입니다.

min([32, 39, 20]) = 20

실수하기 쉬운 부분

현재 집에서 가장 싼 색만 고르면 안 됩니다

현재 집만 보면 가장 싼 색이 좋아 보일 수 있습니다. 하지만 바로 이전 집과 색이 같으면 선택할 수 없습니다.

그래서 현재 비용만 보는 것이 아니라, 이전 집까지의 누적 비용을 함께 봐야 합니다.

dp[house][color]의 의미를 정확히 잡아야 합니다

dp[house][color]는 단순히 해당 집을 해당 색으로 칠하는 비용이 아닙니다.

정확히는 다음 뜻입니다.

house번 집을 color번 색으로 칠했을 때의 최소 누적 비용

이 의미를 잡아야 점화식이 자연스럽게 보입니다.

마지막 정답은 마지막 행에서 찾습니다

모든 집을 칠한 뒤 마지막 집이 어떤 색인지 정해져 있지는 않습니다.

그래서 마지막 행 전체를 보고 가장 작은 값을 고릅니다.

return answer;

복잡도

집 개수를 N, 색 개수를 K라고 하겠습니다.

기본 풀이는 반복문이 세 겹입니다.

집 N개
각 집마다 현재 색 K개
각 현재 색마다 이전 색 K개 확인

따라서 시간 복잡도는 다음과 같습니다.

O(N * K * K)

공간 복잡도는 dp 배열을 사용하므로 다음과 같습니다.

O(N * K)

정리

이 문제의 핵심은 다음 한 문장입니다.

현재 집을 어떤 색으로 칠할지 정한 뒤,
이전 집에서 같은 색만 제외하고 가장 싼 값을 더한다.

처음에는 dp 배열이 어렵게 느껴질 수 있습니다. 하지만 dp[house][color]를 다음 뜻으로 기억하면 훨씬 이해하기 쉽습니다.

house번 집을 color번 색으로 칠했을 때의 최소 누적 비용

결국 이 문제는 모든 선택을 매번 처음부터 다시 계산하는 것이 아닙니다. 이전까지의 최소 비용을 저장해두고, 다음 집 계산에 재사용하는 DP 문제입니다.

비슷한 DP 상태 정의를 Python 코드와 최적화 관점으로도 보고 싶다면 인접한 구역에 같은 색을 쓸 수 없을 때 최소 비용 구하기 글을 이어서 보면 좋습니다.