[15686] 치킨 배달

생각

• N: 도시의 크기
• M: 폐업시키지 않을 치킨집(남길 치킨집)
• 출력: 모든 집 중 치킨 거리의 최솟값
• 치킨 거리: 1에 해당하는 집에서 2에 해당하는 거리들 중 최솟값
• 도시의 치킨 거리: 치킨 거리의 합

이거 조합 문제라는 느낌이 바로 왔다.

1. 조합으로 M개의 치킨집 뽑기
2. M개의 치킨집으로 도시의 치킨 거리 구하기
3. 최소가 되는 도시의 치킨 거리 구하기

그럼 DFS가 생각나는데, 너무 막막했다...^^... swift로 dfs요?

일단 치킨집이랑 집 위치 구하는거까지는 코드구현을 했다..^^
나머지 중요한 풀이쪽은 swift 문법을 좀 더 배우고 나서..

import Foundation

let input = readLine()!.split(separator: " ").map{Int(String($0))!}

let n = input[0]
let m = input[1]

var city: [[Int]] = Array(repeating: Array(repeating: 0,count:n ), count: n)

var house: [(r: Int, c: Int)] = []

var chicken: [(r: Int, c: Int)] = []

for i in 0..<n{
    let line = readLine()!.split(separator: " ").map{Int(String($0))!}
    for j in 0..<n where line[j] == 1 || line[j] == 2{
        if line[j] == 1{
            house += [(r: i, c: j)]
        }else{
            chicken += [(r: i, c: j)]
        }
    }
}

var chickenDis: [[Int]] = Array(repeating: Array(repeating: 0,count:house.count), count: chicken.count)

for i in 0..<chicken.count{
    for j in 0..<house.count{
        chickenDis[i][j] = abs(chicken[i].r - house[j].r) + abs(chicken[i].c - house[j].c)
    }
}

어제 치킨배달을 못풀고 오늘 다시 해본다.
일단 튜플은 Hashable이 아니라서 스택 등에서 못쓰는것? 같았다. (아직 Hashable을 안배워서 모름)
그래서 r,c 를 node라는 구조체로 변경했다.

일단 생각해야할게,

• DFS 대상 그래프는 모든 집의 위치 이런게 아니라, 선택된 치킨집의 종류이다.
• 1,2,3 번째 치킨집이나 2,1,3 번째 치킨집이나 다 똑같은 선택이다.(조합)

1. 치킨집 인덱스로(Int) 조합을 만드는 func dfs 구현
2. 조합에 해당하는 남은 치킨집들로 도시의 치킨 거리 구하기

코드

import Foundation

var selectedChicken = [[Int]]()

func DFS(_ list:[Int],_ n:Int,_ r:Int,_ idx:Int,_ selected: inout [Int]) -> Void{
    if(r == 0){
        selectedChicken.append(selected)
        return
    }
    
    for i in idx..<n{
        selected.append(i)
        DFS(list, n, r-1, i+1, &selected)
        selected.removeLast();
    }
    
}

struct node{
    var r: Int
    var c: Int
}

let input = readLine()!.split(separator: " ").map{Int(String($0))!}

let n = input[0]
let m = input[1]

var city = [[Int]]()

var house = [node]()

var chicken = [node]()

for i in 0..<n{
    let line = readLine()!.split(separator: " ").map{Int(String($0))!}
    for j in 0..<n where line[j] == 1 || line[j] == 2{
        if line[j] == 1{
            house += [node(r: i, c: j)]
        }else{
            chicken += [node(r: i, c: j)]
        }
    }
}

var list = Array<Int>()
for i in 0..<chicken.count{
    list.append(i)
}

var selected = [Int]()

DFS(list, list.count, m, 0, &selected)

func dist(a:[node], b:[node])->Int{
    var sum = 0
    for i in a{
        var distance = 1000
        for j in b{
            distance = min(distance, abs(i.r - j.r) + abs(i.c - j.c))
        }
        sum += distance
    }
    return sum
}

var result = 10000
for l in selectedChicken{
    var s = [node]()
    for i in l{
        s.append(chicken[i])
    }
    result = min(result, dist(a: house, b: s))
}

print(result)

삽질한 보람이 있게 맞았다
dfs쪽만 코드를 참고하고 나머지는 직접 했다.
그래서 그런지 코드가 정말 안좋다...
좀 더 공부해서 간결한 코드를 쓸 수 있게되었음 한다.