백준 알고리즘 15686

입력 : 도시의 크기와 유지할 치킨집의 최대 개수 M, 도시 정보

출력 : 치킨집의 최대 개수(M)만큼을 제외하고 모두 폐점시켰을 때 치킨거리의 최소값

 

풀이

1. 입력받을 때 치킨집과 가정집의 위치를 따로 벡터에 저장한다.

2. 모든 치킨집 중 M개를 고르는 재귀함수를 구현해 M개를 고른 뒤 치킨거리를 구한다.

3. 치킨집을 고른 결과가 중복이 되지 않도록 재귀함수를 구현한다. 중복처리 안하면 시간초과남

 

#include <iostream>
#include <vector>
#include <cmath>
#include <cstdio>

using namespace std;

struct Point{
	int x;
	int y;
};

Point getPoint(int x, int y){
	Point result;
	result.x = x;
	result.y = y;
	
	return result;
}

int city[51][51];
vector<Point> chicken;
bool checkChicken[13];
vector<int> selectedChicken;
vector<Point> house;
int M;

int getChickenDistance(){
	int houseNum = house.size();
	int result = 0;
	
	for(int i=0; i<houseNum; i++){
		int minChickenDistance = 2000;
		for(int j=0; j<M; j++){
			int temp = abs(house[i].x - chicken[selectedChicken[j]].x) + abs(house[i].y - chicken[selectedChicken[j]].y);

			if(temp < minChickenDistance)
				minChickenDistance = temp;
		}
		result += minChickenDistance;
	}
	
	return result;
}

int selectChicken(int n){
	int selectedChickenNum = selectedChicken.size();
	
	if(M == selectedChicken.size())
		return getChickenDistance();
	
	int chickenNum = chicken.size();
	int min = 100000;
	
	for(int i=n; i<=chickenNum - (M-selectedChickenNum); i++) {
		if(checkChicken[i])
			continue;
			
		selectedChicken.push_back(i);
		checkChicken[i] = true;
		
		int result = selectChicken(i+1);
		if(result < min)
			min = result;
		
		selectedChicken.pop_back();
		checkChicken[i] = false;
	}
	
	return min;
}

int main() {
	int N;
	
	scanf("%d %d\n", &N, &M);
	
	for(int i=0; i<N; i++){
		for(int j=0; j<N; j++){
			scanf("%d ", &city[i][j]);
			
			if(city[i][j] == 2)
				chicken.push_back(getPoint(i, j));
			else if(city[i][j] == 1)
				house.push_back(getPoint(i, j));
		}
	}
	
	printf("%d", selectChicken(0));
	
	return 0;
}