백준 15686 치킨 배달

출처: www.acmicpc.net/problem/15686

분류: 완전탐색

---

접근방식

집과 치킨집이 주어지고 집에서 제일 가까운 치킨집까지의 거리가 집의 치킨거리가 됩니다.
모든 집의 치킨 거리를 합친 값이 도시의 치킨거리가 됩니다.
치킨집을 M개 만큼 선택했을 때  최소가 되는 치킨거리를 구하는 문제입니다.

우선 집과 치킨집의 위치를 먼저 저장해두고
치킨집을 M개 골랐을 때의 치킨 거리들을 구하면 됩니다.

 

해결방법

let nm = readLine()!.split(separator: " ").map{Int($0)!}
var board = [[Int]]()
for _ in 0..<nm[0] {
    board.append(readLine()!.split(separator: " ").map({Int($0)!}))
}

typealias Point = (r: Int, c: Int)
var homePoints = [Point]()
var chickenPoints = [Point]()

for r in 0..<board.count {
    for c in 0..<board[0].count {
        if board[r][c] == 1 {
            homePoints.append(Point(r: r, c: c))
        } else if board[r][c] == 2 {
            chickenPoints.append(Point(r: r, c: c))
        }
    }
}

var selected = [Bool](repeating: false, count: chickenPoints.count)
var minimumDistance = Int.max
func selectChickens(idx: Int, selectedCount: Int) {
    if selectedCount == nm[1] {
        // 최소값
        minimumDistance = min(minimumDistance, findDistance())
    }
    
    selected[idx] = true
    selectChickens(idx: idx+1, selectedCount: selectedCount+1)
    selected[idx] = false
    selectChickens(idx: idx+1, selectedCount: selectedCount)
}

func findDistance() -> Int {
    var minDistance = 0
    for home in homePoints {
        var distance = Int.max
        for (idx, chicken) in chickenPoints.enumerated() {
            if selected[idx] {
                distance = min(minDistance, abs(home.r - chicken.r) + abs(home.c - chicken.c))
            }
        }
        minDistance += distance
    }
    return minDistance
}

print(minimumDistance)

 

순열을 구할 때 방문을 체크할 배열을 만들고 인덱스만 가지고 조작하는 방법을 다른 분의 코드를 보고 처음 사용해봤다. 깔끔하고 좋은 방법 같다.