백준 15686

백준 15686 : 치킨 배달

1. 폐업한 치킨집을 1, 2, ..., M개 고르는 경우 모두 고려해 보고 그 중 도시의 치킨 거리가 최소가 되는 경우를 구한다.

cf) MC1 + MC2 + ... + MCM = 2^M (이항계수)

구현할 함수
1. 입력받기
2. 집과 치킨집 위치 찾기
3. M개 중에서 폐업할 치킨 집 고르기
4. 그 경우에 치킨 거리 구하기

정답 코드

#include <iostream>
#include <algorithm>

using namespace std;

int n, m;
int city[51][51];
vector<pair<int, int>> house;
vector<pair<int, int>> chicken, selectedChicken;
vector<int> idx;
int ans=100000;

void input() {
	cin>>n>>m;
	for(int i=0; i<n; i++) {
		for(int j=0; j<n; j++) {
			cin>>city[i][j];
			
			//find house and chickens
			if(city[i][j]==1) {
				house.push_back({j, i});
			}
			else if(city[i][j]==2) {
				chicken.push_back({j, i});
			}
		}
	}

}


//get city chicken distance
int getDistance() {
	int ret=0;
	for(int i=0; i<house.size(); i++) {
		int hy = house[i].first;
		int hx = house[i].second;
		int minDist = 1000000;
		
		for(int j=0; j<selectedChicken.size(); j++) {
			int cy = selectedChicken[j].first;
			int cx = selectedChicken[j].second;
			int dist = abs(cy-hy) + abs(cx-hx);

			minDist = min(minDist, dist);
		}

		ret+=minDist;
	}
	
	return ret;
}


void getSelectedChickens(vector<int> idx) {
	for(int i=0; i<idx.size(); i++) {
		selectedChicken.push_back({chicken[idx[i]].first, chicken[idx[i]].second});
	}	
	
	int temp = getDistance();
	

	ans = min(ans, temp);
	
	
	while(selectedChicken.size()){
		selectedChicken.pop_back();
	}
}


void combi(int start, vector<int> idx, int k) {
	if(idx.size() == k) {
		getSelectedChickens(idx);
		return;
	}
	
	for(int i=start+1; i<chicken.size(); i++) {
		idx.push_back(i);
		combi(i, idx, k);
		idx.pop_back();
	}
	
	return;	
}


void selectClose() {
	for(int i=1; i<=m; i++) {
		combi(-1, idx, i);
	}
}



int main() {	
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);
	
	input();
	
	selectClose(); //select which chickens to close
	
	cout<<ans<<'\n';
	
				
	return 0;
}