백준 15686 치킨배달 c++

//15686
#include <iostream>
#include <vector>
#include <cmath>
#include <cstring>
#include <algorithm>
using namespace std;

int N, M;
int arr[51][51];
int ans;

vector<pair<int, int>> v;
vector<pair<int, int>> house;

void calclulate(vector<pair<int, int>> &chicken){
	int total = 0;
	for (int i = 0;i < house.size();i++) {
		int val = 987654321;
		for (int j = 0;j < chicken.size();j++) {
			val = min(val, abs(chicken[j].first - house[i].first) + abs(chicken[j].second - house[i].second));
		}
		total += val;
	}
	ans = min(ans, total);
}

void choose(int cnt, int start, vector<pair<int, int>>& chicken) {
	if (cnt == M) {
		calclulate(chicken);
	}
	for (int i = start;i < v.size();i++) {
		chicken.push_back({ v[i].first, v[i].second });
		choose(cnt + 1, i + 1, chicken);
		chicken.pop_back();
	}
}

int main(void) {
	cin.tie(0);
	ios::sync_with_stdio(false);
	cin >> N >> M;
	ans = 987654321;
	for (int i = 0;i < N;i++) {
		for (int j = 0;j < N;j++) {
			cin >> arr[i][j];
			if (arr[i][j] == 2) {
				v.push_back({ i, j });
			}
			else if (arr[i][j] == 1) {
				house.push_back({ i, j });
			}
		}
	}
	vector<pair<int, int>> t;
	choose(0, 0, t);

	cout << ans << endl;
	return 0;
}

 

1. permutation이 아닌 dfs를 통해 겹치는 값없이 조합을 구했다.

2. 여러번 틀렸는데 틀린 이유 : ans 값을 초기화하지 않았다. 그리고 val 값을 999999 정도로 초기화했는데 이부분이 문제였던거같다