[백준] 15686 치킨 배달

 

🔒 문제

 

🧠 아이디어

문제를 읽자마자 뵈는 키워드는 '모든 집에서 치킨 집 까지의 최단 거리'다. 

집의 개수가 최대 100개, 치킨집 개수가 최대 13개, 한 집에서 치킨 집까지의 거리 최대 연산량은 100 

따라서 100 * 13 => 1,300으로 백트래킹 풀이가 충분히 가능하겠다는 생각이 들었다.

 

결국 조합이다.

$$ _{13}C_{M} $$

(최대 13개 숫자 중 치킨 집 수 M개를 중복 없이 선택해야한다.)

 

1. 치킨집의 좌표 List keep
2. 모든 집의 좌표 keep 
3. 1과 2를 모두 돌면서 집 사이의 거리 (가로 좌표 차이 + 세로 좌표 차이) 각 치킨 집 좌표별 집과의 거리 keep

13개중 M 개를 고른 치킨집 좌표쌍까지의 거리를 모든 집에서부터 구한다.

모든 집은 모든 치킨 까지의 거리를 구하고 그중 가장 가까운 치킨집을 거리로 택한다.

모든 집에대한 치킨집까지의 거리를 합하면 해당 조합 (13개중 M개)에 대한 치킨집까지의 거리다.

 

$$ _{13}C_{M} $$

개 조합에 대한 모든 집으로부터 치킨집 까지의 거리 중 최소 값을 답으로 택한다.

 

 

실수하기 쉬운 포인트

M의 범위가 [1,13] 이라고 해서 조합 인덱스 범위도 0~12로 잡으면 안된다.

실제로 치킨집의 개수는 얼마나 들어올지 'M'이 결정 하는게 아니라 좌표상 '2'의 개수가 결정한다.

 

🔑 Kotlin Code

import java.io.BufferedReader
import java.io.InputStreamReader
import java.util.*
import kotlin.math.abs
import kotlin.math.min

// IntArray: 좌표 순서대로 갯수
private fun dfs(curIdx: Int, depth: Int, maxDepth: Int, arr: IntArray, answer: IntArray, chickenPointCombinations: LinkedList<IntArray>) {
    if (depth == maxDepth) {
        chickenPointCombinations.add(answer.copyOf())
        return
    }

    for (i in curIdx until arr.size) {
        answer[depth] = arr[i]
        dfs(i + 1, depth + 1, maxDepth, arr, answer, chickenPointCombinations)
    }
}

private fun getDistance(chickenPoint: IntArray, housePoint: IntArray): Int {
    val rowDistance = abs(chickenPoint.first() - housePoint.first())
    val colDistance = abs(chickenPoint.last() - housePoint.last())

    return rowDistance + colDistance
}

fun main() {
    val bufferedReader = BufferedReader(InputStreamReader(System.`in`))
    val (N, M) = bufferedReader.readLine().split(" ").map(String::toInt)

    val map = Array(N){_->
        bufferedReader.readLine().split(" ").map(String::toInt)
    }

    // 치킨집 수 : M ~ 13,
    // 13 Com M [ [], [], []] 구하고 모든 조합에 대해 최소값 나오는게 정답.
    // 1부터 M 까지 숫자에 대해 조합을 구하고 모든 조합에 대한 distance 합 구하면 됨.

    val chickenPointList = LinkedList<IntArray>()
    val housePointList = LinkedList<IntArray>()

    // 모든 포인트 초기화
    for (row in map.indices) {
        for (col in map[row].indices) {
            when (map[row][col]) {
                1 -> housePointList.add(intArrayOf(row, col))
                2 -> chickenPointList.add(intArrayOf(row, col))
                else -> {}
            }
        }
    }

    val arr = IntArray(chickenPointList.size){i-> i}
    val tempCombinationArr = IntArray(M)
    val chickenPointCombinations = LinkedList<IntArray>()


    // checkPointCombinations 엔 모든 13 C m 개 조합 배열이 들어있음 (index 로)
    dfs(0, 0, M, arr, tempCombinationArr, chickenPointCombinations)

    // index: house point index
    // value: distance from house chicken
    val distances = IntArray(housePointList.size){100}

    var answer = Int.MAX_VALUE
    
    // chickenPointCombinations loop
    // (13 개중 M 개) 고르는 총 M 개의 loop 에서 답중 최소 값이 리턴되면됨.
    for (chickenPointIndexes in chickenPointCombinations) {

        // chickenPointIndexes 에는 index 조합이 담겨있음.
        // 이제 M개의 포인트에 대해서 구해보면됨.
        for (chickenPointIdx in chickenPointIndexes) {
            housePointList.forEachIndexed { index, housePoint ->
                // distance has same index of housePointList
                // get distance house - chicken in same combination
                distances[index] = min(distances[index], getDistance(chickenPointList[chickenPointIdx], housePoint))
            }
        }
        // 하나의 조합이 생길 때마다 distance 를 모두 업데이트하며 재계산
        answer = min(answer, distances.sum())

        Arrays.fill(distances, 100)
    }

    print(answer)

}