[C++] 백준 15686번: 치킨 배달

www.acmicpc.net/problem/15686

15686번: 치킨 배달

재귀로 풀지 조합으로 풀지 고민하다가 조합으로 푼 문제이다. 다른 사람들 풀이를 보니 재귀로 많이 풀어낸 것 같다.

 

단순히 치킨거리를 구하는 게 아니라 치킨집을 몇개 선정하고 최소 치킨 거리를 구해야 해서 조금 까다로웠다.

 

처음에 모든 치킨 거리의 수를 계산해서 배열에 저장하고 M개의 치킨집은 벡터에 0 나머지는 1을 넣고 그 조합벡터를

next_permutation을 사용해 풀어냈다.

 

#define _CRT_SECURE_NO_WARNINGS
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

int N, M, ans = 99999;
int map[51][51];
vector<pair<int, int>> home;
vector<pair<int, int>> chick;
int htoc[101][14];
vector<int> open;

int main() {
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	int tmp, tmp2;
	cin >> N >> M;
	for (int i = 0; i < N; i++) {
		for (int j = 0; j < N; j++) {
			cin >> map[i][j];
			if (map[i][j] == 1) {
				home.push_back({ i,j });
			}
			if (map[i][j] == 2) {
				chick.push_back({ i,j });
			}
		}
	}
	for (int i = 0; i < home.size(); i++) {
		for (int j = 0; j < chick.size(); j++) {
			htoc[i][j] = abs(home[i].first - chick[j].first) + abs(home[i].second - chick[j].second);
		}
	}
	for (int i = 0; i < chick.size(); i++) {
		if (i < M) {
			open.push_back(0);
		}
		else {
			open.push_back(1);
		}
	}
	do {
		tmp2 = 0;
		for (int i = 0; i < home.size(); i++) {
			tmp = 9999;
			for (int j = 0; j < chick.size(); j++) {
				if (open[j] == 0) {
					tmp = min(tmp, htoc[i][j]);
				}
			}
			tmp2 += tmp;
		}
		ans = min(tmp2, ans);
	} while (next_permutation(open.begin(), open.end()));

	cout << ans;
	return 0;
}