[백준/코틀린] 15686번: 치킨 배달

링크

15686번: 치킨 배달

풀이

N과 M의 범위가 작기 때문에 브루트포스로 해결할 수 있습니다.
치킨집들 중에서 M개를 선택하는 모든 경우를 백트래킹으로 탐색하며,
각 조합에 대해 도시의 치킨 거리 최솟값을 계산합니다.

코드

import kotlin.math.abs

lateinit var town: List<List<Int>>
lateinit var selected: IntArray
val houses = mutableListOf<Pair<Int, Int>>()
val chickens = mutableListOf<Pair<Int, Int>>()
var ans = Int.MAX_VALUE

fun Pair<Int, Int>.distance(other: Pair<Int, Int>): Int {
    return abs(this.first - other.first) + abs(this.second - other.second)
}

fun backtrack(n: Int, m: Int, d: Int, s: Int) {
    if (m == d) {
        val sum = houses.sumOf { house ->
            selected.map { chickens[it] }.minOf { chicken ->
                chicken.distance(house)
            }
        }

        return run { ans = minOf(ans, sum) }
    }

    (s until n).forEach {
        selected[d] = it
        backtrack(n, m, d + 1, it + 1)
    }
}

fun main() {
    val (n, m) = readln().split(" ").map { it.toInt() }
    town = List(n) { readln().split(" ").map { it.toInt() } }
    selected = IntArray(m)

    for (i in 0 until n) {
        for (j in 0 until n) {
            when (town[i][j]) {
                1 -> houses += i to j
                2 -> chickens += i to j
            }
        }
    }

    backtrack(chickens.size, m, 0, 0)

    println(ans)
}