[백준 15686] 치킨 배달

+ 24.8.17 다시 품

 

더 빨라졌다ㅎㅎ

 

---

그냥 일반적인 조합론 문제이다

집이랑 치킨집의 좌표에 대한 정보를 희소행렬로 저장해주고

조합따지기 위해 재귀 돌리다가 치킨집이 M개가 모였을때의 계산로직만 짜주면 된다

 

---

#include <iostream>
#include <vector>
#include <cmath>
#include <bitset>

#define SIZE 13
#define INF (int)1e9

using namespace std;

int N, M;
vector<pair<int, int>> chicken;
vector<pair<int, int>> home;
bitset<SIZE> visited;

int ans = INF;

void solve(int start, bitset<SIZE> visited) {

	// M개일때 종료
	if (visited.count()==M) {
		int dis = 0;
		int cy, cx, hy, hx;
		int nearest, cur;

		// 모든 집들마다
		for (int i = 0; i < home.size(); i++) {
			hy = home[i].first;
			hx = home[i].second;

			// 제일 가까운 치킨집찾아서 거리 더해주기
			nearest = INF;
			for (int k = 0; k < visited.size(); k++) {
				
				if (visited[k] == 0) continue;

				cy = chicken[k].first;
				cx = chicken[k].second;

				cur = abs(cy - hy) + abs(cx - hx);

				if (nearest > cur) nearest = cur;
			}
			dis += nearest;
		}

		if (ans > dis) ans = dis;

		return;
	}

	// 조합이므로 바로 뒤에꺼부터 탐색
	for (int i = start + 1; i < chicken.size(); i++) {
		visited[i] = 1;
		solve(i, visited);
		visited[i] = 0;
	}
}

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

	cin >> N >> M;
	
	int x;
	for (int i = 1; i <= N; i++) {
		for (int k = 1; k <= N; k++) {
			cin >> x;
			if (x == 1) home.push_back(make_pair(i, k));
			else if (x == 2) chicken.push_back(make_pair(i, k));
		}
	}

	solve(-1, visited);

	cout << ans;

	return 0;
}