[백준] 15686번 치킨 배달

15686번 치킨 배달

---

1. 이해하기

• 치킨 거리는 집과 가장 가까운 치킨집 사이의 거리이다.
• 도시의 치킨 거리는 모든 집의 치킨 거리의 합이다.
• (r1,c1)과 (r2,c2) 사이의 거리는 |r1-r2|+|c1-c2|이다.
• 치킨집 중에서 최대 M개를 고르고, 나머지는 폐업시킨다고 할 때 도시의 치킨 거리가 가장 작게 되는 값을 구하는 문제.
• 모든 치킨집에 대해서 구해보는 완전탐색 문제.

---

2. 구현하기

• 각 집에 대해서 치킨 거리를 구한다.

  int get_chicken_distance(vector<Point> chicken, int x, int y) {
      int ret = get_distance(chicken[0].x,chicken[0].y,x,y);
      int size = chicken.size();
      for(int i = 1; i < size; i++) {
          Point now = chicken[i];
          ret = min(ret,get_distance(now.x,now.y,x,y));
      }
      return ret;
  }

• 도시의 치킨 거리를 구한다.

  int get_city_chicken_distance(vector<Point> house, vector<Point> chicken) {
      int size = house.size();
      int ret = 0;
      for(int i = 0; i < size; i++) {
          Point now = house[i];
          ret += get_chicken_distance(chicken,now.x,now.y);
      }
      return ret;
  }

• 모든 치킨 집에 대해서 M개의 치킨 집을 고르고 그때의 도시의 치킨 거리의 최솟값을 구한다.

  int solve(vector<Point> house, vector<Point> chicken, vector<Point> all_chicken, int index) {
      int size = all_chicken.size();
      if(index > size) return MAX;
      if(index == size) {
          int chic_size = chicken.size();
          if(chic_size == M) return get_city_chicken_distance(house,chicken);
          else return MAX;
      }
      int ret = MAX;
      chicken.push_back(all_chicken[index]);
      ret = min(ret,solve(house,chicken,all_chicken,index+1));
      chicken.pop_back();
      ret = min(ret,solve(house,chicken,all_chicken,index+1));
      return ret;
  }

---

3. 전체 코드

#include <iostream>
#include <vector>
using namespace std;
struct Point{
    int x,y;
};
const int MAX = 987654321;
int map[50][50];
int N,M;

int abs(int a) {
    return (a<0)?-a:a;
}

int get_distance(int x1, int y1, int x2, int y2) {
    return abs(x1-x2)+abs(y1-y2);
}

int get_chicken_distance(vector<Point> chicken, int x, int y) {
    int ret = get_distance(chicken[0].x,chicken[0].y,x,y);
    int size = chicken.size();
    for(int i = 1; i < size; i++) {
        Point now = chicken[i];
        ret = min(ret,get_distance(now.x,now.y,x,y));
    }
    return ret;
}

int get_city_chicken_distance(vector<Point> house, vector<Point> chicken) {
    int size = house.size();
    int ret = 0;
    for(int i = 0; i < size; i++) {
        Point now = house[i];
        ret += get_chicken_distance(chicken,now.x,now.y);
    }
    return ret;
}

int solve(vector<Point> house, vector<Point> chicken, vector<Point> all_chicken, int index) {
    int size = all_chicken.size();
    if(index > size) return MAX;
    if(index == size) {
        int chic_size = chicken.size();
        if(chic_size == M) return get_city_chicken_distance(house,chicken);
        else return MAX;
    }
    int ret = MAX;
    chicken.push_back(all_chicken[index]);
    ret = min(ret,solve(house,chicken,all_chicken,index+1));
    chicken.pop_back();
    ret = min(ret,solve(house,chicken,all_chicken,index+1));
    return ret;
}

int main() {
    cin >> N >> M;
    vector<Point> house,chicken,all_chicken;
    for(int i = 0; i < N; i++) {
        for(int j = 0; j < N; j++) {
            cin >> map[i][j];
            if(map[i][j] == 1) house.push_back({i,j});
            else if(map[i][j] == 2) all_chicken.push_back({i,j});
        }
    }
    int ans = solve(house,chicken,all_chicken,0);
    cout << ans << '\n';
}