[백준/BOJ] 백준 15686번 : 치킨 배달

https://www.acmicpc.net/problem/15686

15686번: 치킨 배달

중복해서 치킨집을 고르지 않기 위해 마지막에 고른 치킨집 번호보다 큰 번호의 치킨집만 골랐고, m개의 치킨집을 골랐을때 도시의 치킨 거리를 구했다.

 

코드

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

int n, m;
vector<pair<int, int>> home;
vector<pair<int, int>> chicken;

//selected:고른 치킨집, last_selected_number:마지막으로 고른 치킨집의 번호
int Solve(vector<pair<int, int>>& selected, int last_selected_number)
{
	int ret = 987654321;

	//m개의 치킨집을 골랐을때
	//도시의 치킨거리를 구한다
	if (selected.size() == m)
	{
		ret = 0;

		//각각의 집마다 치킨 거리를 구해서 더한다
		for (int i = 0; i < home.size(); i++)
		{
			int home_i_result = 987654321;

			for (int j = 0; j < selected.size(); j++)
			{
				home_i_result = min(home_i_result, (abs(home[i].first - selected[j].first) + abs(home[i].second - selected[j].second)));
			}

			ret += home_i_result;
		}

		return ret;
	}

	//치킨집을 고른다
	for (int i = 0; i < chicken.size(); i++)
	{
		//중복해서 치킨집을 고르지 않기 위해 마지막에 고른 치킨집 번호 보다 큰 번호의 치킨집만 고른다
		if (last_selected_number < i)
		{
			selected.push_back(chicken[i]);
			ret = min(ret, Solve(selected, i));
			selected.pop_back();
		}
	}

	return ret;
}

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

	int input;
	vector<pair<int, int>> selected;

	cin >> n >> m;

	for (int i = 0; i < n; i++)
		for (int j = 0; j < n; j++)
		{
			cin >> input;

			if (input == 1)
				home.push_back(make_pair(i, j));

			else if (input == 2)
				chicken.push_back(make_pair(i, j)); //치킨집 번호를 0번부터 매긴다
		}

	cout << Solve(selected, -1);

	return 0;
}