15686 치킨배달

 

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

15686번: 치킨 배달

 

(풀이)

문제의 조건에 치킨집 M의 수는 13개 보다작거나 같다.

폐업 시키지않은 치킨집 수를 최대 M개 고려했을때 치킨 거리가 가장 최소가 될때의 최소값을 찾는문제.

 

치킨집을 폐업 시키는 제한이 없다.

따라서 1개를 폐업시키든 2개를 폐업시키든 폐업시키지 않든 폐업 시키지 않은경우에도 최소거리를 찾을 수 있다.

 

도시 치킨 거리를 가장 최소로 하기 위해서 각 치킨집에서 집들과 가장 가까운 거리의 합을 구하면 된다.

 

그러기 위해 각 치킨집 부터 모든 가정집 까지의 최소 거리를 모두 구해놓고

1~M개의 치킨집이 각각 가정집 1~N개의 거리가 최소가 되는 부분을 더한 총합의 최소값을 한번더 찾는다.

 

1) 치킨 집과 가정집의 모든 거리를 구하기위해

get_Chicken_Distance (가정집 x좌표, 가정집 y좌표, 치킨집x좌표, 치킨집y좌표) 함수를 만들어서 _distacne[가정집][치킨집] 간의 거리를 모두 저장하였다.

 

2)가정집으로부터 1~M번의 치킨집중 최소가 되는 거리들을 찾아서 그 최소값들의 합을 구한다음 출력한다.

 

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

int dx[] = { -1,0,1,0 };
int dy[] = { 0,1,0,-1 };
bool check_chicken[13];
int _distance[100][13];

int map[50][50];
int check_map[50][50];

void get_Chicken_Distance(int house_x, int house_y, int chicken_x, int chicken_y, int from, int to);
void go(int cnt, int idx, int size, int &sum);
int N, M; 
vector<pair<int, int>> house_pos;
vector<pair<int, int>> chicken_pos;
int main(void)
{
	cin >> N >> M;
	//I/O
	for (int i = 0; i < N; ++i)
	{
		for (int j = 0; j < N; ++j)
		{
			cin >> map[i][j];
			if (map[i][j] == 1)
				house_pos.push_back(make_pair(i, j));
			if (map[i][j] == 2)
				chicken_pos.push_back(make_pair(i, j));

		}
	}
	for (int i = 0; i < house_pos.size(); ++i)
	{
		for (int j = 0; j < chicken_pos.size(); ++j)
		{
			get_Chicken_Distance(house_pos[i].first, house_pos[i].second,
				chicken_pos[j].first, chicken_pos[j].second,i,j);

			//check_map ÃʱâÈ­
			for (int x = 0; x < 50; ++x)
			{
				for (int y = 0; y < 50; ++y)
					check_map[x][y] = false;
			}
		}
	}
	int ans = 987654321;
	int _sum = 987654321;
	
	go(0,0, M, _sum);
	ans = min(ans, _sum);

	cout << ans << '\n';
	return 0;
}
void go(int cnt,int idx, int size,int &sum)
{
	if (cnt == size)
	{
		//
		int _sum = 0;
		for (int house = 0; house < house_pos.size(); ++house)
		{
			int tmp_min = 987654321;
			for (int i = 0; i < chicken_pos.size(); ++i)
			{
				if (check_chicken[i])
				{
					tmp_min = min(tmp_min, _distance[house][i]);
				}
			}
			_sum += tmp_min;
		}
		sum = min(sum,_sum);
		return;
	}

	for (int i = idx; i < chicken_pos.size(); ++i)
	{
		if (check_chicken[i] == false)
		{
			check_chicken[i] = true;
			go(cnt + 1,i+1, size, sum);
			check_chicken[i] = false;
			
		}
	}
}
void get_Chicken_Distance(int house_x, int house_y, int chicken_x, int chicken_y,int from, int to)
{
	queue<pair<int, int>> q;
	q.push(make_pair(house_x, house_y));
	check_map[house_x][house_y] = 1;

	while (!q.empty())
	{
		int x = q.front().first;
		int y = q.front().second;
		q.pop();
		if (x == chicken_x && y == chicken_y)
		{
			_distance[from][to] = check_map[x][y]-1;
			return;
		}

		for (int i = 0; i < 4; ++i)
		{
			int xn = x + dx[i];
			int yn = y + dy[i];

			if (xn < 0 || xn >= 50 || yn < 0 || yn >= 50) continue;

			if (check_map[xn][yn] == 0)
			{
				check_map[xn][yn] = check_map[x][y]+1;
				q.push(make_pair(xn, yn));
			}

		}
	}
	
}