[백준] 15686번 치킨 배달

중복을 허용하지 않는 조합을 사용하여 구현해야 한다. 

 

 

초기값을 설정한다. num이 1이면 해당 위치를 house에 넣고 2면 chicken에 넣는다.

 

 

중복을 허용하지 않는 조합의 알고리즘을 사용하여 depth는 현재 폐업하지 않은 치킨집의 갯수를 뜻하고 next는 다음 치킨집의 index 값을 뜻한다. depth == M이면 문제의 조건에 만족하므로 각 집들의 치킨 거리를 계산하여 도시의 치킨 거리를 구한다.

 

 

전체 코드

#include <bits/stdc++.h>

using namespace std;

vector<vector<int>> board(51, vector<int>(51));	// 도시
vector<pair<int, int>> house;	// 집들의 위치
vector<pair<int, int>> chicken;	// 치킨집들의 위치
vector<pair<int, int>> tmp_chicken;	// 치킨집들의 경우의 수
int N, M, answer;

void func(int depth, int next) {
	if (depth == M) {
		int sum = 0; // 도시의 치킨 거리

		// 각 집들의 치킨 거리를 합하여 도시의 치킨 거리를 구한다.
		for (auto cur : house) {
			int mini = 1000000;
			for (auto chick : tmp_chicken) {
				// 해당 집의 치킨 거리
				mini = min(mini, abs(cur.first - chick.first) + abs(cur.second - chick.second));
			}
			sum += mini;
		}

		// 도시의 치킨 거리의 최솟값
		answer = min(sum, answer);
		return;
	}

	for (int i = next; i < chicken.size(); i++) {
		tmp_chicken.push_back(chicken[i]);
		func(depth + 1, i + 1);
		tmp_chicken.pop_back();
	}
}

int main() {
	ios::sync_with_stdio(0);
	cin.tie(0);

	cin >> N >> M;

	answer = 1000000;

	for (int i = 1; i <= N; i++) {
		for (int j = 1; j <= N; j++) {
			int num;
			cin >> num;

			board[i][j] = num;

			switch (num) {
			case 1: {
				house.push_back({ i,j });
				break;
			}
			case 2: {
				chicken.push_back({ i, j });
				break;
			}
			}
		}
	}

	func(0, 0);
	cout << answer;
	
	return 0;
}