[BOJ][15686] 치킨 배달

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

---

 

백트래킹으로 풀 수 있다.

 

도시들을 탐색하면서 집 배열, 치킨집들 배열을 만든다.

치킨집들을 선택해나가면서 집들에서 가장 가까운 치킨집의 거리들을 갱신해나간다.

// dist : i번 집과 치킨집과의 최소 거리
// ind : 치킨집 인덱스,
// cnt : 선택된 치킨집 개수
void backtracking(vector<int> dist, int ind, int cnt) {
	// 경계값 확인

	backtracking(dist, ind + 1, cnt); // ind 번째 선택하지 않고 다음 치킨집 탐색

	pair<int, int> chi = chickens[ind]; // ind 번째 치킨집 좌표 저장
	int sum = 0; // dist 배열 합
	for (int i = 0; i < dist.size(); i++) {
		int x = abs(houses[i].first - chi.first);
		int y = abs(houses[i].second - chi.second);
		dist[i] = min(x + y, dist[i]); // dist 갱신
		sum += dist[i]; 
	}
	answer = min(answer, sum); // 정답 갱신
    
	backtracking(dist, ind + 1, cnt + 1); // ind 번째 선택하고 다음 치킨집 탐색
}

---

소스코드 : github.com/fpdjsns/Algorithm/blob/master/BOJ/15686.%20%EC%B9%98%ED%82%A8%20%EB%B0%B0%EB%8B%AC.cpp