[BOJ][C++] 15686 치킨배달

[BOJ][C++] 15686 치킨배달

풀이

1. 치킨 좌표와 집 좌표를 분류해서 vector에 넣어줍니다.

2. m개의 치킨 집을 선택합니다. 

3. 집마다 가장 가까운 치킨집의 거리를 구해 치킨 거리를 구합니다.

DFS를 이용해서 풀었습니다. 백트래킹을 이용해서 풀었습니다. 다른 풀이 방법들을 찾아보다가 조합을 이용하는 방법이 눈에 띄어서 조합으로도 풀어보았습니다. 조합을 이용하니 더 빠른 속도로 구현 되더라구요.

코드

#define _CRT_SECURE_NO_WARNINGS
#include <cstdio>
#include <vector>
#include <math.h>
using namespace std;
int n, m;
int res = 987654321, del;
int map[51][51];
vector<pair<int, int>> chicken;
vector<pair<int, int>> house;
void DFS(int del_num, int index) {
	if (del_num == del) {
		//거리계산
		//printf("--------------------\n");
		vector<pair<int, int>> c;
		for (int i = 0; i < n; i++) {
			for (int j = 0; j < n; j++) {
				if (map[i][j] == 2) {
					//printf("%d %d\n", i, j);
					c.push_back(make_pair(i, j));
				}
			}
		}
		int val = 0;
		for (int i = 0; i < house.size(); i++) {
			int min = 987654321;
			for (int j = 0; j < c.size(); j++) {
				int tmp = abs(house[i].first - c[j].first) + abs(house[i].second - c[j].second);
				//printf("tmp: %d\n", tmp);
				if (tmp < min) min = tmp;
			}
			val += min;
		}
		//printf("val = %d\n", val);
		if (val < res) res = val;
		return;
	}

	//치킨집 폐업
	for (int i = index; i < chicken.size(); i++) {
		map[chicken[i].first][chicken[i].second] = 0;
		DFS(del_num + 1, i + 1);
		map[chicken[i].first][chicken[i].second] = 2;
	}
}
int main() {
	/*
	1 = 집, 2 = 치킨집
	M개 남기고 폐업

	1. M개 치킨집 선택
	2. 치킨 거리 계산
	3. 가장 작은 치킨 거리 구하기
	*/
	scanf("%d %d", &n, &m);
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < n; j++) {
			scanf("%d", &map[i][j]);
			if (map[i][j] == 2) {
				chicken.push_back(make_pair(i, j));
			}
			else if (map[i][j] == 1) {
				house.push_back(make_pair(i, j));
			}
		}
	}
	del = chicken.size() - m;
	DFS(0, 0);
	printf("%d", res);
}

 

-조합(Combination)을 이용한 방법

#define _CRT_SECURE_NO_WARNINGS
#define MAX 987654321
#include <cstdio>
#include <math.h>
#include <vector>
using namespace std;
int n, m;
int map[51][51];
int res = MAX;
vector<pair<int, int>> chicken;
vector<pair<int, int>> house;
void getDis(int *comb) {
	/*for (int i = 0; i < m; i++) {
		printf("%d ", comb[i]);
	}
	printf("\n");*/
	int dis = 0;
	for (int i = 0; i < house.size(); i++) {
		int min = MAX;
		for (int j = 0; j < m; j++) {
			int tmp = abs(house[i].first - chicken[comb[j]].first) + abs(house[i].second - chicken[comb[j]].second);
			if (tmp < min) min = tmp;
		}
		dis += min;
	}
	if (dis < res) res = dis;
}
void Combination(int comb[], int index, int target, int num) {
	if (num == 0) {
		getDis(comb);
	}
	else if (target == chicken.size()) {
		return;
	}
	else {
		comb[index] = target;
		Combination(comb, index + 1, target + 1, num - 1);
		Combination(comb, index, target + 1, num);
	}
}
int main() {
	scanf("%d %d", &n, &m);
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < n; j++) {
			scanf("%d", &map[i][j]);
			if (map[i][j] == 2) {
				chicken.push_back(make_pair(i, j));
			}
			else if (map[i][j] == 1) {
				house.push_back(make_pair(i, j));
			}
		}
	}
	int *comb = new int[m];
	Combination(comb, 0, 0, m);
	printf("%d", res);
}