[15686번] 치킨배달

15686번: 치킨 배달

 

www.acmicpc.net

/*15686번 치킨배달*/
#include <iostream>
#include <queue>
#include <vector>
#include <math.h>
#include <algorithm>
using namespace std;
struct pnt { int r, c; }house[100], bbq[13];
queue<int>min_Q;
vector<int>combv;
int N, M, Map[50][50];
int house_cnt, bbq_cnt, Min_dis = 1e9;

void cal_min(vector<pnt>alive) {
	int min_temp, temp_dis = 0;
	for (int h = 0; h < house_cnt; h++) {
		min_temp = abs(house[h].r - alive[0].r) + abs(house[h].c - alive[0].c);
		for (int j = 1; j < M; j++) {
			if (min_temp > abs(house[h].r - alive[j].r) + abs(house[h].c - alive[j].c)) {
				min_temp = abs(house[h].r - alive[j].r) + abs(house[h].c - alive[j].c);
			}
		}
		min_Q.push(min_temp);
	}
	while (!min_Q.empty()) {
		temp_dis += min_Q.front();
		min_Q.pop();
	}
	if (Min_dis > temp_dis) {
		Min_dis = temp_dis;
	}
	
}

void comb(int n, int k) {
	
	do {
		vector<pnt>alive;
		for (int i = 0; i < combv.size(); i++) {
			if (combv[i] == 1) {
				alive.push_back(bbq[i]);
			}
		}
		cal_min(alive);
	} while (next_permutation(combv.begin(), combv.end()));
	
}

int main() {
	ios::sync_with_stdio(0), cin.tie(0);
	cin >> N >> M;
	for (int r = 0; r < N; r++) {
		for (int c = 0; c < N; c++) {
			cin >> Map[r][c];
			if (Map[r][c] == 1) {
				house[house_cnt].r = r;
				house[house_cnt].c = c;
				house_cnt++;
			}
			if (Map[r][c] == 2) {
				bbq[bbq_cnt].r = r;
				bbq[bbq_cnt].c = c;
				bbq_cnt++;
			}
		}
	}
	for (int i = 0; i < bbq_cnt - M; i++)combv.push_back(0);
	for (int i = 0; i < M; i++) combv.push_back(1);
	
	comb(bbq_cnt, M);
	cout << Min_dis;
}

 

이 문제의 핵심은 도시에 존재하는 모든 치킨집 중 M개를 고르는 조합을 구하는 것이다.

DFS를 사용해서 풀어도 되지만 STL로 제공하는 next_permutation함수를 사용해 보았다.

next_permutation은 현재 배열의 원소들의 순서를 하나씩 바꿔주는 것으로 반환형은 bool형이다.(next_premutation 참고)

0과 1로 이뤄진 배열을 next_permutation 함수로 계속 조합을 만들어서 구하고자 하는 M개의 치킨집을 선택하도록 구현

next_permutation은 정렬이 된 상태에서 사용해야한다.

ex)