Algorithm/BOJ
백준 15686 치킨 배달
삼쓰 웅쓰
2020. 7. 13. 18:42
728x90
출처: 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)
순열을 구할 때 방문을 체크할 배열을 만들고 인덱스만 가지고 조작하는 방법을 다른 분의 코드를 보고 처음 사용해봤다. 깔끔하고 좋은 방법 같다.