[백준] 1149 (RGB거리)

#1 알고리즘

#1-1 동적 프로그래밍

동적 프로그래밍 (Dynamic Programming), 상향식(Bottom-up) 및 하향식(Top-down) 접근

상향식 동적 프로그래밍을 이용해 풀었다.

 

#1-2 색깔 조건

약간 어렵게 쓰여있는 것 같지만, "모든 지붕은 그 직전 지붕과 색이 달라야 한다"라는 말로 압축된다. 현재 순회중인 지붕의 색과는 다른 색의 지붕을 재귀 호출하는 방식으로 색깔 조건을 구현할 수 있겠다.

 

#1-3 캐싱 객체의 구조와 재귀 호출 가지치기

말 보다 코드가 더 쉬운 문제다. 그냥 바로 #2 코드를 보길 추천한다.

 

먼저 Input으로부터 3가지 색깔에 따른 가격을, 원소가 3개인 배열에 담는다. 그리고 그 배열을 마찬가지로 Input에서 주어지는 지붕의 갯수만큼의 원소를 가지는 부모 배열에 담는다. 즉, 2중 배열(이하 listOfRgbPrice)로 가격을 저장한다.

 

또, 최솟값 저장을 위한 캐싱 객체 또한 listOfRgbPrice와 같은 구조의 2중 배열(이하 cached)로 잡는다. listOfRgbPrice을 인덱스 0부터 순회하는 작업을 시작했다고 가정한다. 지붕이 많을수록 최솟값 도출 작업은 기하급수적으로 늘어날 것이다 (3 × 3 × 3 × 3 × 3 × ...). 따라서 시간 초과를 막기 위한 재귀 호출 트리의 가지치기 작업이 요구된다.

 

가지치기의 기준은, '앞으로 펼쳐질 작업이 100% 동일한 경우'다. 재귀 호출 트리는 'a번째 지붕을 b색으로 칠함'으로 대변되는 노드로 구성되어있을 것이다. 이 때 예를 들어, '7번째 지붕을 초록색으로 칠함'이라는 노드가 있다면 해당 노드는 '8번째 지붕을 빨간색으로 칠함' 그리고 '8번째 지붕을 파란색으로 칠함'이라는 노드를 각각 호출한다.

 

그리고 호출된 '8번째 지붕을 빨간색으로 칠함' 그리고 '8번째 지붕을 파란색으로 칠함' 들도 마지막 지붕에 도달할때까지 하위 노드들을 재귀 호출할 것이다. '7번째 지붕을 초록색으로 칠함'이라는 노드에 의해 재귀호출되는 모든 노드들의 집합은 반드시 하나로 정해진다.

 

이 말은 'a번째 지붕을 b색으로 칠함'이라는 노드에 도착했을 때 이미 해당 노드를 방문하여 최소 가격합 캐싱(= cached[a][b])을 남겨두었다면, 캐싱된 값과 비교하여 이후 벌어질 재귀 호출을 할 지 안할 지 프로그래머가 결정할 수 있다는 말이다.

 

#2 코드 - 코틀린

var houseCount = -1
lateinit var listOfRgbPrice: Array<Array<Int>>
lateinit var cached: Array<Array<Int>>

const val RED = 0
const val GREEN = 1
const val BLUE = 2

fun main() {
    houseCount = readln().toInt()
    listOfRgbPrice = Array(houseCount) { Array(3) { -1 } }
    cached = Array(houseCount) { Array(3) { -1 } }
    for (i: Int in 0..<houseCount) {
        val prices = readln().split(" ")
        listOfRgbPrice[i][RED] = prices[RED].toInt()
        listOfRgbPrice[i][GREEN] = prices[GREEN].toInt()
        listOfRgbPrice[i][BLUE] = prices[BLUE].toInt()
    }

    recursiveTraversal(0, RED, 0)
    recursiveTraversal(0, GREEN, 0)
    recursiveTraversal(0, BLUE, 0)

    println(
        minOf(
            cached[houseCount - 1][RED],
            cached[houseCount - 1][GREEN],
            cached[houseCount - 1][BLUE]
        )
    )
}

fun recursiveTraversal(index: Int, color: Int, previousSum: Int) {
    if (houseCount <= index) {
        return
    }

    val sum = previousSum + listOfRgbPrice[index][color]

    cached[index][color] = if (cached[index][color] == -1) {
        sum
    } else {
        if (cached[index][color] <= sum) { // 가지치기
            return
        } else {
            sum
        }
    }

    when (color) {
        RED -> {
            //recursiveTraversal(index + 1, RED, sum)
            recursiveTraversal(index + 1, GREEN, sum)
            recursiveTraversal(index + 1, BLUE, sum)
        }

        GREEN -> {
            recursiveTraversal(index + 1, RED, sum)
            //recursiveTraversal(index + 1, GREEN, sum)
            recursiveTraversal(index + 1, BLUE, sum)
        }

        BLUE -> {
            recursiveTraversal(index + 1, RED, sum)
            recursiveTraversal(index + 1, GREEN, sum)
            //recursiveTraversal(index + 1, BLUE, sum)
        }
    }
}