[백준/Swift] 15686번: 치킨 배달

 

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

15686번: 치킨 배달

 

백트래킹 문제인데, 실수가 잦아서 헤맸다.

격자가 나오길래 처음엔 BFS인가 했지만 다 읽어보니 격자는 뭐 사용도 안 한다. 

치킨집(chickens)과 집(houses) 배열에 각각 좌표를 넣고 (tuple)

chickens의 조합을 구하면 된다.

여기서 실수한 게 바로, 순열을 구했다는 것..!! 시간초과 발생...

[1,2,4] = [2,4,1] = [4,1,2] = ... 모두 같은 거리의 합이 나오므로 하나만 구하면 됨! 

처음엔 1개부터 n개의 경우의 수로 구했는데 조금 생각해 보니까 치킨집이 최대로 많으면 거리가 줄어든다는 생각이 들었다.

 

 

[0부터 m개의 치킨집 선택한 코드]

//치킨집 1~M개 선택(조합, 순열아님!)
func DFS(_ start: Int, _ selection: [(Int, Int)], _ cnt: Int) {
    if cnt == m {
        answer = min(answer, calculator(selection))
        return
    }
    for i in start..<chickens.count {
        DFS(i+1, selection + [chickens[i]], cnt+1)
        DFS(i+1, selection, cnt+1)
    }
}

경우의 수를 출력하면 아래와 같다

[(1, 2), (2, 2), (4, 4)]
[(1, 2), (2, 2)]
[(1, 2), (4, 4)]
[(1, 2)]
[(2, 2), (4, 4)]
[(2, 2)]
[(4, 4)]
[]

 

 

 

[전체 코드]

import Foundation

/*
 치킨거리: 집과 가장 가까운 치킨집 사이의 거리.
 도시의 치킨 거리 = 모든 집의 치킨 거리 합
 0 빈칸, 1 집, 2 치킨집
 가장 수익을 많이 낼 수 있는 치킨 집 개수는 최대 M
 도시의 치킨 거리가 가장 작게되도록 치킨 집을 고르고, 도시의 치킨 거리의 최솟값을 구해라
 */

//input
let nm = readLine()!.split(separator: " ").map{ Int(String($0))! }
let (n, m) = (nm[0], nm[1])
var arr = [[Int]]()
var chickens = [(Int, Int)]()
var houses = [(Int, Int)]()
var answer = 987654321
for _ in 0..<n {
    arr.append(readLine()!.split(separator: " ").map{ Int(String($0))! })
}
for i in 0..<n {
    for j in 0..<n {
        if arr[i][j] == 1 {
            houses.append((i, j))
        }else if arr[i][j] == 2 {
            chickens.append((i, j))
        }
    }
}

//치킨집 M개 선택(조합, 순열아님!!) -> [1, 2, 4] == [2, 4, 1] == [4, 1, 2] === ...
func DFS(_ start: Int, _ selection: [(Int, Int)]) {
    if selection.count == m { //m개의 치킨집 선택
        answer = min(answer, calculator(selection))
        return
    }
    for i in start..<chickens.count {
        DFS(i+1, selection + [chickens[i]])
    }
}

//치킨집과 집마다의 최소 거리 합 구하기
func calculator(_ selectedChicken: [(Int, Int)]) -> Int {
    var sum = 0
    for house in houses {
        var tmp = 987654321
        for chicken in selectedChicken {
            let minD = abs(chicken.0 - house.0) + abs(chicken.1 - house.1)
            tmp = min(minD, tmp)
        }
        sum += tmp
    }
    return sum
}

DFS(0, [])
print(answer)

 

 

 

 

여기서 윗부분이 0부터 m개의 모든 조합을 선택한 것이고, 아래 코드가 m만 찾아본 결과

엄청난 시간 차이!!