백준 15686 치킨배달

백준 15686
처음에 문제이해를 잘못해서 bfs로 풀다가 실패해서 다시 풀었던 문제
조합을 사용해서 계산을 해주면 된다.

ex) 치킨집 1, 2 ,3 이 있을 때, 최대 2개의 치킨집을 열 수 있다고 가정하면
1 개의 치킨 집을 열었을 때
-> {1}, {2} , {3}
2 개의 치킨 집을 열었을 때
-> {1,2}, {1,3} , {2,3}

1. 열 수 있는 치킨집의 조합 구하기
2. 치킨집의 조합이 선택 됐을 때, 만들어질 수 있는 도시의 치킨 거리 구하기
3. 모든 조합 중에서 가장 작은 도시의 치킨 거리 구하기

=> 모든 조합을 구해서 문제를 풀었는데, 다른 사람의 코드를 보니 애초에 모든 조합(1~m개의 치킨집 조합)을 구할 필요가 없이 치킨집이 많을 수록 도시의 치킨거리는 짧아질 수 밖에 없기 때문에 최대 m개의 치킨집을 사용 가능하다면 m개의 치킨집의 조합만 구하면 된다.

#include<bits/stdc++.h>
using namespace std;
int n, m;
int board[51][51];
vector<pair<int, int>>chk;
vector<pair<int, int>> house;
vector<int> v;
int vis[14];
int sum, ans=15000;
void dfs(int cnt,int idx,int chk_cnt) {

	if (cnt == chk_cnt) {
		//도시의 치킨 거리 계산
		int sum = 0;
		for (int i = 0; i < house.size(); i++) {
			int dist = 15000;
			int x = house[i].first;
			int y = house[i].second;
			for (auto c : v) {
				int nx = chk[c].first;
				int ny = chk[c].second;
				dist = min(dist, abs(x - nx) + abs(y - ny)); // 각 집에서의 치킨 거리
			}
			sum += dist; // 도시의 치킨 거리 
		}
		ans = min(ans, sum); // 최대 m개의 치킨을 선택해서 나올 수 있는 도시의 치킨 거리 최솟값
	}

	for (int i = idx; i < chk.size(); i++) {
		if (vis[i]) continue;
		vis[i] = 1;
		v.push_back(i);
		dfs(cnt + 1, i+1,chk_cnt);
		v.pop_back();
		vis[i] = 0;

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

	cin >> n >> m;

	for (int i = 0; i < n; i++) {
		for (int j = 0; j < n; j++) {
			cin >> board[i][j];
			if (board[i][j] == 1) house.push_back({ i,j });
			else if (board[i][j] == 2) chk.push_back({ i,j });
		}
	}

	for (int i = 1; i <= m; i++) {
		dfs(0, 0, i);
	}

	cout << ans << '\n';

}