[백준/BOJ] 15686번: 치킨 배달

문제

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

15686번: 치킨 배달

해설

브루트 포스(Brute Force) 문제이다.

문제에서 원하는 것은 결국, 모든 집에 대해 가장 가까운 치킨집까지의 거리의 합이다.

 

내가 푼 문제 해결 과정(알고리즘)은 다음과 같다.

• 맵을 입력받으면서, 집과 치킨집의 좌표를 저장해둔다.
• 모두 저장했다면, dfs를 수행하며 남길 치킨집을 선택한다.
  • visited 배열을 방문처리를 해준 후의 갯수를 세고, 이를 다시 false로 바꾸면서, 이 치킨집을 선택하지 않고 넘어가는 경우도 생각해준다.
• M개의 치킨 집을 선택했다면, 거리를 계산하여 저장한다.
• 2번째와 3번째 과정을 반복하면서 도시의 치킨 거리가 가장 작게 되는 값을 출력하면 된다.

소스 코드

import java.util.*
import kotlin.collections.ArrayList
import kotlin.math.abs

private var n = 0
private var m = 0
private var ans = Int.MAX_VALUE
private val home = ArrayList<Pair<Int, Int>>()
private val chicken = ArrayList<Pair<Int, Int>>()
private lateinit var map: Array<IntArray>
private lateinit var visited: BooleanArray

fun main() = with(System.`in`.bufferedReader()) {
    var st = StringTokenizer(readLine())
    n = st.nextToken().toInt()
    m = st.nextToken().toInt()

    map = Array(n) { IntArray(n) }
    visited = BooleanArray(13)

    repeat(n) { i ->
        st = StringTokenizer(readLine())
        repeat(n) { j ->
            map[i][j] = st.nextToken().toInt()
            if(map[i][j] == 1) home.add(Pair(i, j))
            else if(map[i][j] == 2) chicken.add(Pair(i, j))
        }
    }

    dfs(0, 0)
    println(ans)
}

private fun dfs(idx: Int, cnt: Int) {
    if(cnt == m) {
        var totalDistance = 0
        for(i in home.indices) {
            var dist = Int.MAX_VALUE
            for(j in chicken.indices) {
                if(visited[j]) dist = minOf(dist, distance(home[i], chicken[j]))
            }

            totalDistance += dist
        }

        ans = minOf(ans, totalDistance)
        return
    }

    if(idx == chicken.size) return

    visited[idx] = true
    dfs(idx + 1, cnt + 1)
    visited[idx] = false
    dfs(idx + 1, cnt)

}

private fun distance(house: Pair<Int, Int>, chicken: Pair<Int, Int>): Int {
    return abs(house.first - chicken.first) + abs(house.second - chicken.second)
}