백준 - 치킨배달(Swift)

백준 - 치킨배달(Swift)

 

 

 문제 설명

 

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

15686번: 치킨 배달

 

 나의 풀이

 

입력조건이 작은 것을 보고 완전탐색을 생각했고 이 때문에 조합을 이용해서 문제를 풀었다.

하지만 문제를 푸는데 조금 오래걸렸는데 그 이유가 집들에 대해서 가장 가까운 치킨집을 구하는 것이 아닌 치킨집들에 대해서 가장 가까운 집을 찾았던 것이다. 이 문제는 모든 집에서 가장 가까운 치킨집까지의 거리를 구하는 것인데 말이다.

이 부분을 해결하니 문제가 바로 풀렸다.

 

import Foundation

let input = readLine()!.components(separatedBy:" ").map{Int($0)!}

let N = input[0], M = input[1]
var map = [[Int]]()
var chickens = [(Int, Int)]()
var houses = [(Int, Int)]()
var result = Int.max
for _ in 0..<N {
    let arr = readLine()!.components(separatedBy:" ").map{Int($0)!}
    map.append(arr)
}
for i in 0..<N {
    for j in 0..<N {
        if map[i][j] == 2 {
            chickens.append((i,j))
        } else if map[i][j] == 1 {
            houses.append((i,j))
        }
    }
}

let combinedChickens = combination(chickens, M)

for chicks in combinedChickens {
    var sum = 0
    for x in houses {
        var minVal = Int.max
        for y in chicks {
            minVal = min(minVal, distance(x,y))
        }
        sum += minVal
    }
    result = min(result, sum)
}

print(result)


func combination<T>(_ targetArr: [T], _ n : Int) -> [[T]] {
    var results = [[T]]()
    if targetArr.count < n { return results }
    func cycle(_ idx: Int, _ arr: [T]) {
        if arr.count == n {
            results.append(arr)
            return
        }
        for i in idx..<targetArr.count {
            cycle(i+1, arr + [targetArr[i]])
        }
    }
    cycle(0, [])
    return results
}

func distance(_ chicken: (Int, Int), _ house: (Int, Int)) -> Int {
    return abs(chicken.0 - house.0) + abs(chicken.1 - house.1)
}