치킨 배달(x)

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

#include <iostream>
#include <vector>

using namespace std;

int n, m;
vector<vector<int>> map;
vector<pair<int, int>> chicken;
vector<pair<int, int>> home;
vector<vector<int>> chickenList;

void Combi(int start, vector<int> v)
{
	if(v.size() == m)
	{
		chickenList.push_back(v);
		return;
	}

	for (int i = start+1; i < chicken.size(); i++)
	{
		v.push_back(i);
		Combi(i, v);
		v.pop_back();
	}
}

int main()
{
	cin >> n >> m;
	map.resize(n, vector<int>(n, 0));
	for (int i = 0; i < n; i++)
	{
		for (int j = 0; j < n; j++)
		{
			cin >> map[i][j];
			if (map[i][j] == 1)
				home.push_back({ i,j });
			else if (map[i][j] == 2)
				chicken.push_back({ i,j });
		}
	}
	int result = 987654321;
	vector<int> v;
	Combi(-1, v);

	for (vector<int> list : chickenList)
	{
		int ret{};
		for (pair<int, int> h : home)
		{
			int m = 987654321;
			for (int c : list)
			{
				int dist = abs(h.first - chicken[c].first) + abs(h.second - chicken[c].second);
				m = min(m, dist);
			}
			ret += m;
		}
		result = min(result, ret);
	}

	cout << result << endl;
}

• 이 문제는 조합을 이용해 푸는 문제이다
• 그 이유는 맵에서 m개의 치킨집에서 집들의 거리를 구해 다른 m개의 치킨집에서 집들의 거리와 비교해 최소 거리를 구하는 문제이다
• 그중 m개의 치킨집은 순서가 상관이 없기 때문에 조합을 이용해 푸는 문제가 되는 것이다
• 다시 코드로 돌아가 map을 입력받아 집과, 치킨집, 거리를 나타내는데 이때 map[i][j] == 1, 2일때 vector<pair<int, int>> 변수인 home, chicken에 현재 위치인 i,j를 저장해준다
• Combi()에 넘겨줄 인자를 위해 vector<int> 변수 v를 만들어주고, -1과 함께 넘겨준다
• Combi()는 조합을 구할 함수로 v.size()가 m과 같다면 chickenList에 현재 v를 저장해준뒤 return해준다
• 이는 map 안에 치킨집을 m개 골라 그 조합을 만들어 저장해 주는 것이다
• 그렇지 않다면 start+1부터 chicken.size()보다 작을동안 반복문을 반복하면서 v에 i를 저장해고, Combi() 를 호출해준다
• 함수를 탈출하게 되면 v에 i를 빼주면서 여러 조합을 만들어 만들어진 조합을 저장해주는 것이다
• Combi()를 완전히 탈출하면 만들어진 조합인 chickenList을 이용해 for each를 사용할 것이다
• 이 조합을 가지고 집과의 거리를 비교해 최소 거리를 비교해 구할 것이다
• 집을 저장한 home도 for each를 이용해 반복할 것이고 chickenList를 이용한 list역시 한번 더 for each를 만들어준다
• 여기서 h.first와 chicken[c].first, h.second와 chicken[c].second를 빼고 절댓값을 구해준 값을 더해 현재 치킨집에서 현재 집까지의 거리를 구해 dist에 저장해준다
• 이 값을 m과 비교해 더 작은 값을 m에 저장해준다
• 이렇게 되면 현재 집을 기준으로 조합으로 만든 치킨집들의 거리를 구해 그중 더 작은 값을 m에 저장하는 것이다
• list의 반복이 끝나면 ret에 m을 누적해 더해주어 현재 치킨집 조합을 기준으로 모든 집들의 최소 거리를 ret에 구하는 것이다
• home의 반복도 끝나면 result와 ret값을 비교해 작은 값을 result에 저장해준다
• 이는 조합들마다 구한 거리를 비교해 더 작은 값을 result에 저장하는 것이다