BOJ-17404 RGB거리 2 Swift

문제

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

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

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

입력

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

출력

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

 

접근방법: DP

해당문제를 풀기전 규칙을 먼저 이해해야한다. 규칙은 단순하다.

직선 위 N개의 집이 주어졌을 때, 서로 인접한 집과의 색이 같지 않고, 첫번째와 마지막의 집의 색이 같으면 안된다.

직선을 원으로 만들어 첫번째와 마지막 집을 인접시키면 모든 집은 인접한 집과 다른 색을 갖는다는 점과 같지만

이 문제에선 이 방식은 사용하지않지만 규칙을 이해하는데 쉬웠다.

 

첫번째 집부터 마지막집까지 색칠하는 과정을 거치는데 첫번째와 마지막집의 색이 같으면 안되므로 첫번째집의 색을 알고 있어야한다.

이를 DP방식을 이용하여 풀려면 이전까지 색칠한 비용을 알고 이용하여 그다음 집까지 색칠비용을 구한다.

 

인접한 집과 색이 같으면 안되므로 

첫번째 집이 빨강이면 두번째 집은 파랑과 초록이 가능하다

두번째 집이 파랑이라면 세번째 집은 빨강과 초록이 가능하다.

세번째 집이 초록이라면 네번째 집은 빨강과 파랑이 가능하다.

 

주어진 비용을 2차원 배열로 저장하면 빨강: 0, 초록: 1, 파랑: 2 인덱스를 갖는 배열이 된다.

위 방식을 사용하면 dp배열을 아래와 같이 정의할 수 있다.

dp[n][0]: n번째 집을 빨강으로 색칠한 최소비용

dp[n][1]: n번째 집을 초록으로 색칠한 최소비용

dp[n][2]: n번째 집을 파랑으로 색칠한 최소비용

dp[n][0] = arr[n][0] + min(dp[n-1][1], dp[n-1][2]) (arr: 색칠비용이 담긴 2차원배열)

 

이렇게 마지막 집까지 모두 색칠했을 때, 마지막 집과 첫번째 집의 색이 다른 경우의 비용을 갱신하여 값을 구한다.

 

코드로 구현하면 다음과 같다.

import Foundation

// 입력받기
let N = Int(readLine()!)!
var arr = [[0]]
let INF = 100000000
var ans = INF
for _ in 1...N {
    arr.append(readLine()!.split(separator: " ").map{Int(String($0))!})
}

// 첫번째 집이 어떤색을 칠하는지? 가 기준이 된다.
// 집이 나열된 선분을 순환구조로 나타낸다면, 인접한 집과의 색은 같으면 안된다.
// 첫번째 집을 세가지 색 모두 칠해보고 색칠비용의 최솟값을 구한다.
for i in 0...2 {
    // dp[i][j]: i번째집을 j색으로 칠했을 때의 최소비용
    var dp = Array(repeating: Array(repeating: 0, count: 3), count: N+1)
    // 첫번째 집과 마지막집의 색이 같으면 안되므로, 우리는 첫번째 집의 색을 기억하고 있어야한다.
    // 따라서 첫번째 집의 색 이외의 경우의수는 임의의 최댓값을 넣는다.
    for j in 0..<3 {
        if i == j {
            dp[1][j] = arr[1][j]
        } else {
            dp[1][j] = INF
        }
    }
    
    // 규칙에따라 현재집은 이전의 집과 다른색을 칠해야한다.
    // n번째 집까지 색칠한 최소비용: n-1번째까지 칠한 최소비용 + n번째 집의 색칠비용
    for j in 2...N {
        dp[j][0] = arr[j][0] + min(dp[j-1][1], dp[j-1][2])
        dp[j][1] = arr[j][1] + min(dp[j-1][0], dp[j-1][2])
        dp[j][2] = arr[j][2] + min(dp[j-1][0], dp[j-1][1])
    }
    // 첫번째 집과 마지막번째 집의 색이 같지 않다면, 최소비용을 갱신한다.
    for k in 0..<3 {
        if i != k {
            ans = min(ans, dp[N][k])
        }
    }
}
print(ans)