[BOJ][삼성기출] 15686. 치킨 배달

풀이

#include <iostream>
#include <math.h>

using namespace std;

typedef struct point{
	int x;
	int y;
} point;

int N, M;
int map[51][51];
point house[101];
point chick[14];
int num_house = 0, num_chick = 0;
int is_open[14];
int rst = 100000;

point make_point(int x, int y);
void dfs(int m, int depth);
int cal_distance(int x1, int y1, int x2, int y2);
int get_min_distance();
point make_point(int x, int y);

int main(){
	cin >> N >> M;
	for(int i = 1; i <= N; i++){
		for(int j = 1 ; j <= N; j++){
			cin >> map[i][j];
			if(map[i][j] == 1){
				house[++num_house] = make_point(i, j);
			} else if(map[i][j] == 2){
				chick[++num_chick] = make_point(i, j);
			}
		}
	}
	
	for(int i = 1; i <= num_chick; i++) dfs(i, 1);
	cout << rst << endl;	
}

void dfs(int m, int depth){
	is_open[m] = 1;
	if(depth == M){
		int d = get_min_distance();
		if(rst > d) rst = d;
		is_open[m] = 0;
		return ;
	}
	for(int i = m + 1; i <= num_chick; i++){
		dfs(i, depth + 1);
	}
	is_open[m] = 0;
}

int cal_distance(int x1, int y1, int x2, int y2){
	return abs(x1 - x2) + abs(y1 - y2);
}

int get_min_distance(){
	int sum = 0;
	for(int h = 1; h <= num_house; h++){
		int min_d = 100000;
		for(int c = 1; c <= num_chick; c++){
			if(is_open[c]){
				int curr_d = cal_distance(house[h].x, house[h].y, chick[c].x, chick[c].y);
				if(min_d > curr_d) min_d = curr_d; 
			}
		}
		sum += min_d;
	}
	return sum;
}	
				 	
point make_point(int x, int y){
	point p;
	p.x = x; p.y = y;
	return p;
}