[BOJ15686][C++] 치킨 배달

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

15686번: 치킨 배달

문제

 

해결

🎈Key Point🎈

입력받은 치킨집 중에서 M개를 뽑기 -> 조합(백트래킹) 사용

뽑은 치킨집 중에서 다시 치킨 거리가 최소일 때를 구함

 

입력받은 치킨집 중에서 M개로 이루어진 묶음을 모두 저장한 다음 모든 묶음을 돌면서 치킨 거리를 계산하고, 그 중 최소거리를 정답으로 출력하면 된다.

 

[전체 코드]

 

#include <iostream>
#include <vector>
#include <algorithm>
#include <cmath>

using namespace std;

typedef pair<int, int> pi;

int N, M;
vector<pi> house;
vector<pi> chicken;
vector<vector<pi>> selected;
int result = 1e9;

vector<pi> one_pack;
void Combination(int k) {

	if (one_pack.size() == M) {
		selected.push_back(one_pack);
	}
	else if (k == chicken.size()) {  }
	else {
		one_pack.push_back(chicken[k]);
		Combination(k + 1);
		one_pack.pop_back();
		Combination(k + 1);
	}
}

int Distance(pi h, vector<pi> pack) {
	int minDis = 1e9;
	
	for (auto p : pack) {
		int dis = abs(h.first - p.first) + abs(h.second - p.second);
		minDis = min(minDis, dis);
	}

	return minDis;
}

int main(void) {
	ios::sync_with_stdio(0);
	cin.tie(0);

	// 입력
	cin >> N >> M;
	for (int i = 0; i < N; i++) {
		for (int j = 0; j < N; j++) {
			int num;
			cin >> num;
			if (num == 1) house.push_back({ i, j });
			if (num == 2) chicken.push_back({ i, j });
		}
	}
	// 

	Combination(0);		// M개로 이루어진 치킨집 조합을 모두 저정한다.

	for (auto pack : selected) {
		int disSum = 0;

		for (auto h : house) {
			disSum += Distance(h, pack);	// 하나의 치킨집 조합에 대해 치킨 거리 계산
		}

		result = min(result, disSum);
	}

	cout << result;
}