백준 15686번 치킨배달 재풀이

 

20분 소요.

벡터 명에 select, home과 같은 단어 사용하지 말것.

 

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

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

vector<pair<int, int> > home;
vector<pair<int, int> > chicken;
vector<pair<int, int> > select;


void DFS(int idx, int cur)
{
	if (cur == M)
	{
		int sum = 0;

		for (int i = 0; i < home.size(); i++)
		{
			int minx = 987654321;
			for (int j = 0; j < select.size(); j++)
			{
				if (abs(home[i].first - select[j].first) + abs(home[i].second - select[j].second) < minx)
				{
					minx = abs(home[i].first - select[j].first) + abs(home[i].second - select[j].second);
				}
			}
			sum += minx;
		}

		if (sum < mina)
		{
			mina = sum;
		}

		return;
	}

	for (int i = idx + 1; i < chicken.size(); i++)
	{
		select.push_back({ chicken[i].first,chicken[i].second });
		DFS(i, cur+1);
		select.pop_back();
	}
}

int main(int argc, char** argv)
{

	cin >> N >> M;
	mina = 987654321;

	for (int i = 1; i <= N; i++)
	{
		for (int j = 1; j <= N; j++)
		{
			cin >> arr[i][j];
		}
	}


	for (int i = 1; i <= N; i++)
	{
		for (int j = 1; j <= N; j++)
		{
			if (arr[i][j] == 1)
			{
				home.push_back({ i,j });
			}
			else if (arr[i][j] == 2)
			{
				chicken.push_back({ i,j });
			}
		}
	}

	int c = chicken.size();
	for (int i = 0; i < c; i++)
	{
		select.push_back({ chicken[i].first,chicken[i].second });
		DFS(i, 1);
		select.pop_back();
	}



	cout << mina << endl;



	return 0;//정상종료시 반드시 0을 리턴해야합니다.
}