[백준 BOJ] 15686번 - 치킨 배달 (C++)

15686번: 치킨 배달 (acmicpc.net)

15686번: 치킨 배달

 

먼저 떠오른 생각은 'M의 수보다 치킨 집의 수가 더 많았을 때의 경우 어떻게 할 것인가'였다. M보다 치킨 집이 많으면 M의 개수가 되도록 추출을 해야하는데 이때 순서는 필요없으므로 조합을 사용해야겠다라고 생각했다. 이후 치킨 거리를 계산할 때 미리 치킨 집과 일반 집의 좌표를 vector<pair<int,int>> 타입으로 저장해놓고 뽑은 치킨 집에 대해서 계산해주면 편할 거 같다고 생각했다.

조합의 경우 백트래킹을 이용했고 조합이 어렵게 느껴지면 그냥 같은 수 없이 크기 순으로 이루어진 수열이라고 생각하면 될 거 같다.

#include <iostream>
#include <vector>
#include <cmath>
#define pii pair<int,int>
using namespace std;
int N,M;
vector<pii> home;
vector<pii> chi;
vector<int> combi;
int chi_count = -1;
int mindist = 987654321;
vector<int> result(100,-1);
int visit[13];
void cal()
{
	//for(int i = 0 ;i<M;i++)
	//	cout<<combi[i]<<" ";
	//cout<<endl;
	for(int i = 0; i<home.size(); i++)
		result[i]=987654321;
	for(int i =0; i<home.size(); i++)
	{
		for(int j = 0; j<combi.size(); j++)
		{
			int tmp=abs(home[i].first-chi[combi[j]].first)+abs(home[i].second-chi[combi[j]].second);
			if(result[i]>tmp)
				result[i]=tmp;
		}
	}
	int sum = 0;
	for(int i = 0; i<home.size();i++)
	{
		sum+=result[i];
	}
	if(sum<mindist)
		mindist=sum;
}

void dfs(int lev)
{
	if(combi.size()==M)
	{
		cal();
		return;
	}
	for(int i = lev; i<=chi_count; i++)
	{
		combi.push_back(i);
		dfs(i+1);
		combi.pop_back();
	}
}

int main()
{
	cin>>N>>M;
	int get;
	for(int i = 0; i<N; i++)
	{
		for(int j = 0; j<N; j++)
		{
			cin>>get;
			if(get==1)
				home.emplace_back(i,j);
			else if(get==2)
			{
				chi.emplace_back(i,j);
				chi_count++;
			}
		}
	}
	dfs(0);
	cout<<mindist<<endl;
	return 0;
}