[코딩테스트]🍗치킨 배달 - 백준 15686

문제링크

문제링크

난이도

골드 5

유형

백트래킹, 구현

소요시간

1시간

회고

구현하는 건 어렵지 않았는데 조합, 재귀 함수에대한 연습이 필요함을 느꼈다. 3년 전에 풀어본 문제인데 처음 본 문제 같았다.

코드

    typealias P = (r: Int, c: Int)
    let nm = readLine()!.split(separator: " ").map { Int($0)! }
    let (N, M) = (nm[0], nm[1])

    var houses = [P]()
    var chickens = [P]()

    // 좌표 수집
    (0..<N).forEach { r in
        let row = readLine()!.split(separator: " ").map { Int($0)! }
        (0..<N).forEach { c in
            if row[c] == 2 {
                chickens.append( (r, c) )
            } else if row[c] == 1 {
                houses.append( (r, c) )
            }
        }
    }

    // 조합
    var visited = Array(repeating: false, count: 13)
    var answer = [Int]()

    comb(0, 0)

    func comb(_ start: Int, _ count: Int) {
        if count == M {
            let picked = visited
                .indices
                .filter { visited[$0] }
                .map { chickens[$0] }

            let result = houses.map { house in
                var minDistance = Int.max

                picked.forEach { chicken in
                    minDistance = min(minDistance, distance(chicken, house))
                }

                return minDistance
            }.reduce(0, +)

            answer.append(result)
        }

        (start..<chickens.count).forEach{ i in
            if !visited[i] {
                visited[i] = true
                comb(i, count + 1)
                visited[i] = false
            }
        }
    }

    func distance(_ lhs: P, _ rhs: P) -> Int {
        abs(lhs.r - rhs.r) + abs(lhs.c - rhs.c)
    }

    print(answer.min()!)