NxN 2차원 배열에서 치킨집을 M개 골라 도시의 치킨 거리를 최소값으로 만드는 문제이다.
여기서 치킨 거리
는 집과 가장 가까운 치킨집 사이의 거리
이고, 도시의 치킨 거리
는 모든 집의 치킨 거리의 합이다.
치킨 거리는 |x1-x2| + |y1-y2|
로 구할 수 있다.
두 좌표만 알면 거리를 구할 수 있기에 굳이 BFS를 쓰지 않아도 됬었는데, 습관적으로 쓰다가 시간 초과가 나버려 문제를 푸는데 시간이 조금 더 걸렸다.
코드는 아래와 같다.
- 치킨 집 중에서 M개를 선택한다.
- 선택된 치킨집 중 각각의 집으로부터 가장 가까운 치킨집까지의 거리를 구해서 더한다.
- 합이 최소인 경우를 구한다.
#include <iostream>
#include <vector>
#include <string.h>
using namespace std;
int N, M;
int myMap[50][50];
bool visited[50][50];
int dist[50][50];
int dx[4] = {1, -1, 0, 0};
int dy[4] = {0, 0, -1, 1};
struct p
{
int x;
int y;
};
p make_p(int x, int y)
{
p temp;
temp.x = x;
temp.y = y;
return temp;
}
vector<p> chicken;
vector<p> house;
int arr[15];
int answer;
void select_chicken(int idx)
{
if (idx == M)
{
vector<p> selected;
for (int i = 0; i < M; i++)
{
selected.push_back(chicken[arr[i]]);
}
int sum = 0;
for (int i = 0; i < house.size(); i++)
{
int min = INT16_MAX;
for (int j = 0; j < selected.size(); j++)
{
int dis = abs(house[i].x - selected[j].x) + abs(house[i].y - selected[j].y);
if (dis < min)
min = dis;
}
sum += min;
}
if (sum < answer)
answer = sum;
}
else
{
for (int i = 0; i < chicken.size(); i++)
{
if (idx == 0 || arr[idx - 1] < i)
{
arr[idx] = i;
select_chicken(idx + 1);
}
}
}
}
int main()
{
cin >> N >> M;
for (int i = 0; i < N; i++)
{
for (int j = 0; j < N; j++)
{
int x;
cin >> x;
if (x == 2)
chicken.push_back(make_p(i, j));
if (x == 1)
house.push_back(make_p(i, j));
}
}
answer = INT16_MAX;
select_chicken(0);
cout << answer << endl;
}