• 문제 : https://www.acmicpc.net/problem/15686

---

1. 문제 접근

문제를 풀 때, 완전 탐색 방법으로 설계 => 시간복잡도 계산 => 만약 가능하다면 완탐으로 구현!

• 완전 탐색을 한다고 가정하면, 다음과 같은 최대 경우의 수 나온다.
  • 모든 치킨집에서 M개의 치킨 선택 x N개의 집에서 가장 가까운 치킨집 선택
  • 13C7 x 100 x 7 = 1201200
  • 주어진 문제의 조건으로 충분히 가능!

---

2. 시행착오

• 없음

---

3. 코드 및 풀이

3.1 풀이

• 우선, 치킨집들 중 M개를 선택하는 것을 구현한 다음,
• 해당 치킨 조합들 중에서 도시의 치킨 거리 계산
  • 이때, 하나의 조합에서 도시의 치킨 거리를 계산할 때도 완전탐색으로 계산(ex. 집이 100개, M이 7이라면, 700번 계산해서, 집1, 집2, ... 집 100과 치킨집과의 거리 최솟값을 일일히 구한 후, 모두 합하면 도시의 치킨 거리 계산 완료)
  • 그리고 ret = min(ret, sum);코드를 통해, 모든 치킨집에 대해서 최소의 도시의 치킨 거리를 찾기 위해 갱신

#include <bits/stdc++.h>
using namespace std;

int N, M, tmp;

// 최솟값을 고르므로
int ret = 1e6;

// N x N matrix만들지 말고 치킨집, 집 좌표만 저장
vector<pair<int, int>> chicken;
vector<pair<int, int>> tmp_chicken;
vector<pair<int, int>> house;

// 맨하탄 거리 계산 함수
int calc_distance(pair<int, int>h, pair<int, int> c) {
    return abs(h.first - c.first) + abs(h.second - c.second);
}

// 치킨집의 한 조합이 선택되었을 때, 해당 치킨집에서 구할 수 있는 도시의 치킨 거리 계산 및 최솟값 갱신하는 함수
void go(){
    vector<int> tmp_house_dist;
    
    for(auto it_h: house){
        int min_dist = 1e6;
        for(auto it_c: tmp_chicken) {
            min_dist = min(min_dist, calc_distance(it_h, it_c));
        }
        // 각 집마다 가장 거리가 짧은 치킨집의 거리를 더함
        tmp_house_dist.push_back(min_dist);
    }
    // 도시의 치킨 거리 계산
    int sum = accumulate(tmp_house_dist.begin(), tmp_house_dist.end(), 0);
    
    ret = min(ret, sum);
}

// M개의 치킨 선택 => 해당 치킨 조합 선택 후 go() 호출
void chooseChicken(int idx, int cnt){
    if(cnt == M) {
        go();
        return;
    }
    for(int i = idx; i < chicken.size(); i++){
        tmp_chicken.push_back(chicken[i]);
        chooseChicken(i+1, cnt+1);    
        tmp_chicken.pop_back();
    }
    
}

int main(){
    cin >> N >> M;
    for(int i = 0; i < N; i++){
        for(int j = 0; j < N; j++){
            cin >> tmp;
            if(tmp == 1) house.push_back({i, j});
            if(tmp == 2) chicken.push_back({i, j});
        }
    }
    
    chooseChicken(0, 0);
    cout << ret;
}

3.2 다른 방향

• 먼저 가능한 치킨집 조합인 경우를 모두 구한 후 => 거리 계산하는 방법도 있음
• M개의 치킨집 조합 코드를 다음과 같이 설계 가능
• vector v를 인자로 넣어서, m개가 맞다면, 모든 조합 경우의 수를 보관하는chickenList에 push

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();
    }
    return;
}

vector<int> v;
combi(-1, v);

---

Reference