백준 15686_치킨 배달(C++)

 

https://www.acmicpc.net/problem/15686

15686번: 치킨 배달

[문제 풀이]

조합을 이용하여 문제를 풀었습니다.

 

도시의 치킨집 중에 M개를 조합을 이용하여 골라줍니다. M개의 치킨집이 선택되었다면 치킨 거리의 최솟값을 구해 주었습니다. 그 후 최솟값이 도시의 가장 작은 치킨 거리인가를 확인해 주었습니다.

[코드]

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

using namespace std;

int map[51][51];
int dx[4] = {0, 1, 0, -1};
int dy[4] = {1, 0, -1, 0};

vector<pair<int, int>> store;
vector<pair<int, int>> home;
int home_distance[250] = { 987654321, };
int check[13] = { 0, };

int N, M;
int result = 987654321;

void select(int, int);
void cal();

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] == 1) {
				home.push_back(make_pair(i, j));
			}

			if (map[i][j] == 2)
				store.push_back(make_pair(i, j));

		}
	}

	for (int i = 0; i < store.size(); i++) {

		check[i] = 1;
		select(i, 1);
		check[i] = 0;
	}

	printf("%d\n", result);

}

void cal() {

	int sum = 0;

	for (int i = 0; i < home.size(); i++)
		home_distance[i] = 987654321;

	for (int i = 0; i < 13; i++) {

		if (check[i] == 1) {

			for (int j = 0; j < home.size(); j++) {

				int distance = abs(home[j].first - store[i].first) + abs(home[j].second - store[i].second);

				if (home_distance[j] > distance)
					home_distance[j] = distance;
			}

		}
	}

	for (int i = 0; i < home.size(); i++)
		sum += home_distance[i];

	if (sum < result)
		result = sum;

}

void select(int idx, int cnt) {

	if (cnt == M) {
		cal();
		return;
	}

	if (idx + 1 == store.size())
		return;

	for (int i = idx + 1; i < store.size(); i++) {

		check[i] = 1;
		select(i, cnt + 1);
		check[i] = 0;
		
	}

}