[백준 15686] 치킨배달 c++

15686번 - 치킨배달

문제 이해

치킨집, 집의 위치가 주어진다.
모든 집에 대해 집에서 가장 가까운 치킨집까지의 거리의 합을 구하면 도시의 치킨거리가 된다.
치킨집중 M개만 남길 때, 도시의 치킨거리의 최소값을 구해야 한다.

접근

백트래킹으로 해결이 가능하다.

정답 코드

#include <bits/stdc++.h>
#define fastio             \
  ios::sync_with_stdio(0); \
  cin.tie(0);              \
  cout.tie(0)
#define X first
#define Y second
#define all(x) x.begin(), x.end()
#define INF (~0U >> 2)
#define MAX 50

using namespace std;
typedef long long ll;
typedef pair<int, int> pii;

int N, M, ans = INF;
vector<pii> chicken, house;

int dist(pii a, pii b) {
  return abs(a.X - b.X) + abs(a.Y - b.Y);
}

// chicken 중 M개를 고른 후 치킨 거리의 합을 반환
int getDist(vector<int>& v) {
  int ret = 0;
  for (auto h : house) {
    int d = INF;
    for (auto i : v) {
      d = min(d, dist(h, chicken[i]));
    }
    ret += d;
  }
  return ret;
}

void dfs(int idx, vector<int>& v) {
  if (v.size() == M) {
    ans = min(ans, getDist(v));
    return;
  }

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

void solve() {
  cin >> N >> M;
  int point;
  for (int i = 0; i < N; i++)
    for (int j = 0; j < N; j++) {
      cin >> point;
      if (point == 1)
        house.push_back({i, j});
      else if (point == 2)
        chicken.push_back({i, j});
    }

  vector<int> v;
  dfs(0, v);
  cout << ans << '\n';
}

int main() {
  fastio;
  solve();

  return 0;
}