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

문제 바로가기

---

⛳문제⛳

1. 크기가 N×N인 도시는 (r, c) 좌표에 1×1크기의 칸으로 구성돼 있고, r과 c는 1부터 시작한다.

2. 도시의 각 칸은 치킨집(2)과 빈칸(0), 집(1) 중 하나이며 각 숫자로 주어진다.

3. 치킨 거리란 어떤 집과 그 집에서 가장 가까운 치킨집 사이의 거리이며 거리는 각 좌표의 차이(절댓값) 합이다.

4. 도시의 치킨 거리는 도시 내 모든 집 각각의 치킨거리 합이다.

5. 도시의 치킨 집 중 M개 점포를 남기고 나머지는 폐업시키고자 한다.

6. 치킨집 중에서 최대 M개를 골라 도시의 치킨 거리가 최소가 됐을 때, 도시의 치킨 거리를 구해보자.

---

🧨입력조건🧨

2 ≤ N ≤ 50

1 ≤ M ≤ 13

---

✨풀이✨

1. 좌표 순서대로 입력을 받는다.

2. 입력된 수가 1 또는 2라면 미리 선언해둔 벡터 house, shops에 해당 좌표를 저장한다.

3. 조합 \(\left(\begin{array}{c}shops.size()\\shops.size()-M\end{array}\right)\)의 각 경우의 수를 계산하여 벡터 closedShops에 저장한다.

  - 조합을 구현하는 방법은 여기를 참고했다.

  - 위 조합은 어떤 치킨집을 폐업시킬지 선택하는 것이다. 남는 매장이 M개가 되도록.

4. closedShops의 각 요소에 대해 다음(5~6)을 반복한다.

  5. 각 집별 치킨거리를 구하는데, closedShops에 해당하는 점포는 제외하고 계산한다.

  6. 각 집별 치킨거리를 모두 한 한 도시의 치킨 거리가 계산되면, 다른 경우의 값과 비교하여 최소값을 갱신한다.

7. 결과를 출력하면 끝.

---

🎈코드🎈

디버그 코드

#include <iostream>
#include <utility>
#include <vector>

using namespace std;

#define EL "\n"
#define INF 987654321
#define FOR(i, K) for(int i = 0; i < K; i++)

int N, M;
int shopIdx[13];
bool isSelected[13];
vector<pair<int, int>> house, shops;
vector<vector<int>> closedShops;

int min(int lhs, int rhs) {
	if (lhs < rhs)
		return lhs;
	return rhs;
}

void combine(int idx, int cnt) {
	if (cnt == shops.size() - M) {
		vector<int> list;
		for (int i = 0; i < 13; i++) {
			if (isSelected[i])
				list.push_back(i);
		}
		closedShops.push_back(list);
		return;
	}
	for (int i = idx; i < shops.size(); i++) {
		if (isSelected[i]) continue;
		isSelected[i] = true;
		combine(i, cnt + 1);
		isSelected[i] = false;
	}
}

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

	cin >> N >> M;

	FOR(r, N) {
		FOR(c, N) {
			int i;
			cin >> i;
			if (i == 1) {
				house.push_back(make_pair(r + 1, c + 1));
			}
			else if (i == 2) {
				shops.push_back(make_pair(r + 1, c + 1));
			}
		}
	}

	int CL_Table[100][13];
	int _r = 0, _c = 0;
	for (auto& h : house) {
		_c = 0;
		for (auto& c : shops) {
			CL_Table[_r][_c] = abs(h.first - c.first) + abs(h.second - c.second);
			_c++;
		}
		_r++;
	}

	cout << EL;
	combine(0, 0);
	int minCL = INF;
	for (auto& closed : closedShops) {
		int cityCL = 0;
		for (auto& h : house) {
			int houseCL = INF;
			for (int i = 0; i < shops.size(); i++) {
				for (int idx : closed)
					if (i == idx) {
						cout << "* ";
						goto NEXT;
					}
				cout << 2 << " ";
				houseCL = min(houseCL, abs(h.first - shops[i].first) + abs(h.second - shops[i].second));
			NEXT:;
			}
			cityCL += houseCL;
			cout << EL;
		}
		cout << EL;
		minCL = min(minCL, cityCL);
	}

	cout << EL;
	FOR(r, house.size()) {
		FOR(c, shops.size()) {
			cout << CL_Table[r][c] << " ";
		}
		cout << EL;
	}

	cout << EL;
	cout << minCL << EL;

	return 0;
}

 

 

#include <iostream>
#include <utility>
#include <vector>

using namespace std;

#define EL "\n"
#define INF 987654321
#define FOR(i, K) for(int i = 0; i < K; i++)

int N, M;
bool isSelected[13];
vector<pair<int, int>> house, shops;
vector<vector<int>> closedShops;

int min(int lhs, int rhs) {
	if (lhs < rhs)
		return lhs;
	return rhs;
}

void combine(int idx, int cnt) {
	if (cnt == shops.size() - M) {
		vector<int> list;
		for (int i = 0; i < 13; i++) {
			if (isSelected[i])
				list.push_back(i);
		}
		closedShops.push_back(list);
		return;
	}
	for (int i = idx; i < shops.size(); i++) {
		if (isSelected[i]) continue;
		isSelected[i] = true;
		combine(i, cnt + 1);
		isSelected[i] = false;
	}
}

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

	cin >> N >> M;

	FOR(r, N) {
		FOR(c, N) {
			int i;
			cin >> i;
			if (i == 1) {
				house.push_back(make_pair(r + 1, c + 1));
			}
			else if (i == 2) {
				shops.push_back(make_pair(r + 1, c + 1));
			}
		}
	}

	combine(0, 0);
	int minCL = INF;
	for (auto& closed : closedShops) {
		int cityCL = 0;
		for (auto& h : house) {
			int houseCL = INF;
			for (int i = 0; i < shops.size(); i++) {
				for (int idx : closed)
					if (i == idx) {
						goto NEXT;
					}
				houseCL = min(houseCL, abs(h.first - shops[i].first) + abs(h.second - shops[i].second));
			NEXT:;
			}
			cityCL += houseCL;
		}
		minCL = min(minCL, cityCL);
	}

	cout << minCL << EL;

	return 0;
}