99클럽 코테 스터디 23일차 TIL: 완전탐색 + 백트래킹

문제

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

풀이

치킨집을 최대 M개를 골랐을 때, 도시의 치킨 거리의 최솟값을 출력하는 문제

치킨집을 고르는 것은 조합을 구하는 것을 의미한다.
조합을 구하는 코드는 다음과 같이 짰다.

func dfs(i: Int, selected: [(Int, Int)]) {
    if selected.count == m {
        result = min(result, getDistance(coord: selected))
        return
    }

    for index in i..<chicken.count {
        dfs(i: index + 1, selected: selected + [chicken[index]])
    }
}

동일한 치킨집을 뽑으면 안되기 때문에 뽑은 치킨집 다음 치킨집 부터 탐색할 수 있도록 index 값을 파라미터로 받았다.
치킨집을 뽑았으면, 특정집에서 가장 가까운 치킨집을 고르는 작업을 진행해야한다.

한 집에서 모든 치킨집을 확인해봐야 한다.

해당 코드는 다음과 같이 구현했다.

func getDistance(coord: [(Int, Int)]) -> Int {
    var distance = 0
    for h in house {
        var minDistance = Int.max
        for c in coord {
            minDistance = min(minDistance, abs(h.0 - c.0) + abs(h.1 - c.1))
        }
        distance += minDistance
    }
    return distance
}

여기서 받는 coord 파라미터가 치킨집을 뽑은 조합을 의미한다.
전체 코드는 다음과 같다.

소스코드

후기

치킨집을 뽑는 부분에서 백트래킹 기법이 들어간다.
그리고 한 집에서 모든 치킨집에 대한 거리를 구해서 최소 거리를 구해야 하는 문제

크게 어렵지 않은 문제였다.