[Swift] 백준 치킨 배달 15686

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

 

1. 문제이해

최대 M개의 치킨집만 도시에 존재해야 한다고 했을 때, 도시의 치킨 거리(모든 집의 치킨 거리의 합)의 최소 값을 구하기

2. 접근방법

1. 집 좌표, 치킨집 좌표 조합 만들기
   1. 치킨 집 좌표를 백트래킹으로 완전 탐색
   2. 가장 가까운 치킨집 찾기
2. 도시의 치킨거리 최솟값 구하기

3. 코드

import Foundation

func solution(){
    let input = readLine()!.split(separator: " ").map{Int(String($0))!}
    let N = input[0]
    let M = input[1]
    var map = [[Int]]()
    for _ in 0..<N{
        map.append(readLine()!.split(separator: " ").map{Int(String($0))!})
    }
    
    var chicken = [(Int, Int)]() // 치킨집 좌표
    var house = [(Int, Int)]() // 집 좌표
    
    // 집 좌표와 치킨 집 좌표 저장하기
    for i in 0..<N{
        for j in 0..<N{
            if map[i][j] == 1{ // 집
                house.append((i,j))
            }else if map[i][j] == 2{ // 치킨집
                chicken.append((i,j))
            }
        }
    }
    
    // 활성화된 치킨집 좌표(스택)
    var chickenEnable = [(Int,Int)]()
    var result = Int.max
    
    func chickenDistance() -> Int{
        var sum = 0
        for h in house{
            var minDistance = Int.max
            for c in chickenEnable{
                minDistance = min(minDistance, abs(h.0 - c.0) + abs(h.1 - c.1))
            }
            sum += minDistance
        }
        return sum
    }
    
    func dfs(index: Int){
        if M  == chickenEnable.count{ // 활성화된 치킨집 좌표가 M개 채워졌을 때
            result = min(chickenDistance(), result)
            return
        }
        for i in index..<chicken.count{
            chickenEnable.append(chicken[i]) // push
            dfs(index: i+1)
            chickenEnable.removeLast() // pop
        }
    }
    dfs(index: 0)
    print(result)
}
solution()