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

 

치킨 거리의 합을 가장 작게 만드는 문제이다. 치킨집이 10개 있고 치킨집을 최대 M개 고를 수 있다고 할 때 10 C M 조합의 모든 경우에 따른 거리의 합을 살펴보면 된다.

 

문제해결방법

1.우선 초기의 도시 상태를 입력받는다. 입력 받을 때 만약 치킨집이 있다면 vector에 치킨집의 좌표를 push한다.

2. 치킨 집의 가능한 모든 조합에 대해 도시의 치킨 거리를 구한다.(최솟값을 저장한다.)

 

 

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

int arr[51][51];
vector<pair<int,int> > V;
int N=0;
int M=0;
int result=987654321;
void DFS(int count, int pre);
int main(void)
{
	cin>>N>>M;
	
	for(int i=1; i<=N; i++)
	{
		for(int j=1; j<=N; j++)
		{
			cin>>arr[i][j];
			if(arr[i][j]==2)
			{
				V.push_back({i,j});
			}
		}
	}
	
	DFS(0,-1);
	
	cout<<result;
	return 0;
}

int visited[50];

void DFS(int count, int pre)
{
	if(count==M)//백터에서 치킨집을 꺼내서 거리를 찾는다. 
	{
		int distance=0;
		
		for(int i=1; i<=N; i++)
		{
			for(int j=1; j<=N; j++)
			{
				if(arr[i][j]==1)
				{
					int temp=987654321;
					for(int k=0; k<50; k++)
					{
						if(visited[k]==1)
						{
							int x=i-V[k].first;
							int y=j-V[k].second;
							if(x<0)
							{
								x=(-x);
							}
							if(y<0)
							{
								y=(-y);
							}
							if(temp>x+y)
							{
								temp=x+y;
							}
						}
					}
					distance+=temp;
				}
			}
		}
		if(distance<result)
		{
			result=distance;
		}
		
	}
	for(int i=0; i<V.size(); i++)
	{
		if(visited[i]==0&&i>pre)
		{
			visited[i]=1;
			DFS(count+1,i);
			visited[i]=0;
		}	
	}
}