문제 소개 📌

문제 링크 📢

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

문제 풀이 📝

입력에서 볼 수 있듯이 도시에 존재하는 치킨집의 최대 개수는 13개가 최대이다. 또한 N이 최대 50이라 NxN배열도 큰 배열이 아니기 때문에 완전탐색으로 해결이 가능하다.
우선 존재하는 모든 집과 치킨집의 좌표를 벡터에 저장한다. 그 다음엔 M개의 치킨집을 골라내야하고 골라낼 때 순서는 상관이 없으므로 조합을 사용하여 골라낸 뒤 조합을 위해 따로 만들어놓은 벡터에 저장한다.
이후 그 벡터에 저장된 정보에 따라 각 집에서부터 골라놓은 치킨집까지의 최소거리를 구한다. 이를 조합의 수만큼 반복, 최소값을 갱신하면서 도시의 치킨거리를 구할 수 있다!

코드

#include<iostream>
#include<algorithm>
#include<vector>
#include<set>
#include<string>
#include<cmath>

#define INF 1e9;
using namespace std;
typedef pair<int, int> pii;
vector<pii> v, cPos,hPos;
int visited[55][55];
int map[55][55];
int N, M, minDist, sum, minSum = INF;
void go()
{
	if (v.size() == M) // M개의 조합을 선정한 뒤
	{
		sum = 0;
		for (int i = 0; i < hPos.size(); i++)
		{
			minDist = INF;			
			for (int j = 0; j < v.size(); j++) 
			{
				int dist = abs(hPos[i].first - v[j].first) + abs(hPos[i].second - v[j].second);
				minDist = min(minDist, dist);//치킨거리를 구한다
			}
			sum += minDist;
		}
		minSum = min(minSum, sum); // 최소 도시의 치킨거리를 갱신!
	}
	for (int i = 0; i < cPos.size(); i++)
	{
       // 가능한 모든 경우를 탐색하기 위해 좌표를 조합을 사용하여 확인한다!
		if (!v.empty() && v.back() >= cPos[i]) continue;
		if (visited[cPos[i].first][cPos[i].second] == 0)
		{
			visited[cPos[i].first][cPos[i].second] = 1;
			v.push_back(cPos[i]);
			go();
			visited[cPos[i].first][cPos[i].second] = 0;
			v.pop_back();
		}
	}
}
int main()
{
	cin >> N >> M;
	
	for (int i = 1; i < N + 1; i++)
	{
		for (int j = 1; j < N + 1; j++)
		{
			cin >> map[i][j];
			if (map[i][j] == 1) hPos.push_back({ i,j });
			if (map[i][j] == 2) cPos.push_back({ i,j });
		}
	}
	
	go();
	cout << minSum;
	return 0;
}