15686 치킨 배달

15686 치킨 배달 (c++)

문제

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

접근 방식

구현, 백트래킹, 브루트 포스

1. NxN의 마을에서 치킨집을 M개까지 줄였을 때, 각 집에서 가장 가까운 치킨집까지의 거리 합의 최소는?
2. 일단 치킨집 M개를 백트래킹으로 선별
3. 2에서 구해진 M개의 치킨집으로 각 집까지의 거리 중 최소를 구함
4. 3에서 구해진 최소거리들의 합을 answer와 비교하여 더 작다면 answer를 갱신

문제 풀이

#pragma GCC optimize("Ofast")
#include <iostream>
#include <vector>
#define MAX 987654321
using namespace std;

inline int Min(int A, int B) { return A < B ? A : B; }
inline int ABS(int A) { return A < 0 ? -A : A; }
inline int CalcDist(pair<int, int> A, pair<int, int> B) { return ABS(A.first - B.first) + ABS(A.second - B.second); }

int N, M, num, answer = MAX;
vector<pair<int,int>> houses, chickens;
vector<int> target = {};

void Check()
{
	vector<int> cost = vector<int>(houses.size(), MAX);
	int sum = 0;
	for (int j = 0; j < houses.size(); ++j)
	{
		for (int i = 0; i < target.size(); ++i)
		{
			cost[j] = Min(cost[j], CalcDist(chickens[target[i]], houses[j]));
		}
		sum += cost[j];
	}
	
	answer = Min(answer, sum);
}

void BT(int startPos)
{
	if (target.size() == M)
	{
		Check();
        return;
	}

	for (int i = startPos; i < chickens.size(); ++i)
	{
		target.push_back(i);
		BT(i + 1);
		target.pop_back();
	}
}

void Init()
{
	cin >> N >> M;

	for (int i = 0; i < N; ++i)
	{
		for (int j = 0; j < N; ++j)
		{
			cin >> num;
			if (num == 1) houses.push_back({ i, j });
			else if (num == 2) chickens.push_back({ i, j });
		}
	}
}

void Solve()
{
	BT(0);
}

int main()
{
	ios::sync_with_stdio(0);  cin.tie(0);
	
	Init();

	Solve();

	cout << answer << '\n';

	return 0;
}

다시 생각해 볼 점

1. 진짜 엄청 고민 많이 했고, 삽질도 많이 했다.
2. 해도 해도 안풀려서 알고리즘 분류를 열어보았고, 브루트 포스와 백트래킹을 발견
3. 나는 처음엔 치킨집들의 값을 매겨서 정렬 후 가장 높은 값의 치킨집 M개를 남기려고 했는데,
   브루트 포스로 푼다면 그냥 모든 경우의 수 중 치킨 거리가 가장 작은 값을 픽하면 되는거였다.
4. 앞으로 일단 브루트 포스를 써보고 안되면 최적화 하는 식으로 하자.