백준 15686번 치킨 배달 - 스위프트(Swift) 풀이

1. M개 이하의 치킨집을 고르는 모든 경우에 대해 도시의 치킨 거리를 계산한다. 

---

1. M개 이하의 치킨집을 고르는 모든 경우에 대해 도시의 치킨 거리를 계산한다. 

 단순 구현 문제이다. 브루트포스로도 시간 안에 풀 수 있다.

 M개 이하의 치킨집을 이미 골랐다고 가정했을 때, 도시의 치킨 거리를 구하는 데는 O(2N * 13)이 든다. M개 이하의 치킨집을 고르는 경우의 수는 적어도 2^13보다는 적으므로 최종 시간 복잡도는 O(2N * 13 * 2^13) = O(2^14 * 13 * N)이고, N=50이므로 연산 횟수 10,649,600으로 AC를 받기에 충분한 시간 복잡도이다.

 

---

import Foundation

typealias Chicken = (row: Int, col: Int)
typealias ChickenDist = (index: Int, dist: Int)

var N = 0, M = 0
var houses = [House]()
var chickens = [Chicken]()
var result = 987654321

class House {
    let row: Int
    let col: Int
    var chickenDist: [ChickenDist]              // 모든 치킨집까지의 거리
    
    init(row: Int, col: Int) {
        self.row = row
        self.col = col
        self.chickenDist = []
    }
    
    func minChickenDist(mask: Int) -> Int {     // 선택한 치킨집을 mask로 나타낼 때 가장 가까운 치킨집 사이의 거리
        for cd in chickenDist {                 // 오름차순 정렬되어 있으므로 앞에서부터 차례로 탐색
            if mask & (1 << cd.index) != 0 { return cd.dist }
        }
        
        return 2501
    }
}

func calcCityChickenDist(mask: Int) -> Int {    // 도시의 치킨 거리
    var sum = 0
    
    houses.forEach{ sum += $0.minChickenDist(mask: mask) }
    
    return sum
}

// 현재까지 index번째 치킨집까지 고려했고, count개의 치킨집을 골랐으며, 어떤 치킨집들을 골랐는지를 비트마스크 mask로 나타냄
func pickMChickens(index: Int, count: Int, mask: Int) {
    if index == chickens.count {                                // 모든 치킨집을 다 고려했을 때
        guard count <= M else { return }                        // M개 이하의 치킨집을 고른 경우
        result = min(result, calcCityChickenDist(mask: mask))   // 그때의 도시의 치킨 거리 계산 후 최소값 갱신
        return
    }
    
    pickMChickens(index: index+1, count: count, mask: mask)     // index번째 치킨집을 고르지 않음
    
    if count < M {                                              // index번째 치킨집을 고름
        pickMChickens(index: index+1, count: count+1, mask: mask | (1 << index))
    }
}

func solution() {
    let input = readLine()!.split(separator: " ").map{ Int(String($0))! }
    N = input[0]
    M = input[1]
    
    for i in 0..<N {
        let city = readLine()!.split(separator: " ").map{ Int(String($0))! }
        for j in 0..<N {
            if city[j] == 1 {
                houses.append(House(row: i, col: j))
            } else if city[j] == 2 {
                chickens.append((i, j))
            }
        }
    }
    
    for house in houses {
        for (index, chicken) in chickens.enumerated() { // 어떤 집에서 모든 치킨집까지의 거리를 구해둠
            let dist = abs(chicken.row - house.row) + abs(chicken.col - house.col)
            house.chickenDist.append((index, dist))
        }
        
        house.chickenDist.sort(by: { $0.1 < $1.1 })     // 어떤 집에서 각 치킨집까지의 거리를 오름차순 정렬해둠
    }
    
    pickMChickens(index: 0, count: 0, mask: 0)
    
    print(result)
}

solution()