BOJ 15686 : 치킨 배달

[정답 코드]

#include <iostream>
#include <vector>
#include <algorithm>
#include <cstring>
#include <cstdlib>
using namespace std;

const int MAX = 100000000;

//디버깅용 프린트 함수
void print(vector<pair<int, int>>&v) {
	int s = v.size();
	for (int i = 0; i < s; i++) {
		cout << "#" << i << "   " << v[i].first << v[i].second << "\n";
	}
}

int N, M;
vector<pair<int, int>> map; //집 위치, (y,x)
vector<pair<int, int>> c_map; //치킨집 위치, (y,x)
vector<pair<int, int>> chosen; //선택된 치킨집 위치 저장
int answer = MAX;

int cal() {
	int s = map.size();
	int dy, dx;
	int sum_dist = 0;
	for (int i = 0; i < s; i++) {
		int min_dist = MAX;
		for (int k = 0; k < chosen.size(); k++) {
			dy = abs(map[i].first - chosen[k].first);
			dx = abs(map[i].second - chosen[k].second);
			int dist = dy + dx;
			//cout << "map_y:" << map[i].first << "map_x" << map[i].second << "c_map_y" << chosen[k].first << "c_map_x" << chosen[k].second << "dist" << dist << "\n";
			if (dist < min_dist) {
				min_dist=dist;
			}
		}
		sum_dist += min_dist;
	}
	return sum_dist; //도시의 치킨 거리 반환
}

void choose(int idx, int cnt) {
	int tmp;
	if (cnt == M) {
		//치킨거리 계산
		tmp = cal();
		if (tmp < answer) answer = tmp;
		return;
	}
	int n = c_map.size();
	if (idx == n)return;
	chosen.push_back({ c_map[idx] });
	choose(idx + 1, cnt + 1);
	chosen.pop_back();
	choose(idx + 1, cnt);
}

int main() {
	cin >> N >> M;
	for (int i = 0; i < N; i++) {
		for (int j = 0; j < N; j++) {
			int temp;
			cin >> temp;
			if (temp == 1) {
				map.push_back({ i,j });
			}
			if (temp == 2) {
				c_map.push_back({ i,j });
			}
		}
	}

	choose(0, 0);

	cout << answer << "\n";

	//print(map);
	//print(c_map);

	return 0;
}