문제 링크 (opens new window)

풀이

1. 조합 구현
2. 치킨집과 집 위치를 튜플로 저장
3. 치킨집 조합으로 생성된 배열 순회하며 각 집마다 더 짧은 치킨거리 계산
4. 최종 도시 치킨거리 계산 후 최솟값 리턴

import Foundation

let nm = readLine()!.split(separator: " ").map { Int($0)! }; let n = nm[0]; let m = nm[1]
var adj: [[Int]] = .init(repeating: .init(repeating: 0, count: n), count: n)

var chickenPos: [(Int, Int)] = []
var homePos: [(Int, Int)] = []

for i in 0..<n {
    adj[i] = readLine()!.split(separator: " ").map { Int($0)! }
    for (index ,pos) in adj[i].enumerated() {
        if pos == 1 {
            homePos.append((i + 1, index + 1))
        } else if pos == 2 {
            chickenPos.append((i + 1, index + 1))
        }
    }
}

func combination<T>(_ elements: [T], _ k: Int) -> [[T]] {
    var results: [[T]] = []

    func combi(_ index: Int, _ now: [T]) {
        if now.count == k {
            results.append(now)
            return
        }

        for i in index..<elements.count {
            combi(i + 1, now + [elements[i]])
        }
    }
    combi(0, [])
    return results
}

var minSum = Int.max

// 1. 치킨집 1 ~ m개중 생존할 치킨집 갯수
// 2. 치킨집 i개일때 치킨집 위치 조합
// 3. 집 위치 순회 -> 각 집마다 i개 치킨집 중 더 가까운 곳을 치킨거리로 설정
for i in 1...m {
    for chicken in combination(chickenPos, i) {
        var sum = 0
        for home in homePos {
            var shortCut = Int.max
            for pos in chicken {
                shortCut = min(shortCut, abs(pos.0 - home.0) + abs(pos.1 - home.1))
            }
            sum += shortCut
        }
        minSum = min(minSum, sum)
    }
}

print(minSum)