백준 2098 외판원 순회문제

https://www.acmicpc.net/problem/2098

2098번: 외판원 순회

 

import kotlin.math.min

class Solution {
    val IMPOSSIBLE = 100000000
    var nOfCity: Int = 0
    lateinit var city: Array<IntArray>
    lateinit var dp: Array<IntArray>

    fun input() {
        nOfCity = readLine()!!.toInt()
        city = Array(nOfCity) { intArrayOf() }
        dp = Array(1.shl(nOfCity)) { IntArray(nOfCity) { -1 } }
        for (i in (0 until nOfCity)) {
            city[i] = readLine()!!.split(" ").map { it.toInt() }.toIntArray()
        }
    }

    fun solve(currentCity: Int, visit: Int): Int {
        // base
        if (visit == 1.shl(nOfCity) - 1) {
            if(city[currentCity][0] == 0)
                return IMPOSSIBLE
            return city[currentCity][0]
        }

        if(dp[visit][currentCity] != -1){
            return dp[visit][currentCity]
        }

        var mini = IMPOSSIBLE

        // 아직 방문안한 도시 방문.
        for (i in (0 until nOfCity)) {
            if (visit.and(1.shl(i)) == 0 && city[currentCity][i] != 0) { // 방문안한 케이스
                val newVisit = visit.or(1.shl(i))
                val newCost = solve(i, newVisit) +  city[currentCity][i]
                mini = min(mini, newCost)
            }
        }
        dp[visit][currentCity] = mini

        return mini
    }
}

fun main() {
    val solution = Solution()
    solution.input()
        println(solution.solve(0, 1.shl(0)))
}

 

간단한 문제인데, 아직 탑다운 DP에 덜 익숙한 것 같다. 

큰 문제를 작은 문제로 분해해서 풀 때, 작은 문제와 큰 문제의 정확한 분리가 필요하다. 

 

예를 들어서

'현재 위치까지 올 때 까지의 비용 + 현재 위치에서 다음 위치로 넘어갈 때의 비용' 을 함수 매개변수로 주면

작은 문제가 큰 문제에 의존성을 띠게되므로 결과를 왜곡한다.