백준, BOJ, 15686번, 치킨 배달 : C++ [CPP] ★★★★★

백트래킹 중에 가장 중요한게 시간인데

백트래킹을 가지치기해서 최대한 시간을 줄여야한다.

왜냐하면.. 백트랙킹은 가짓수가 기하급수적으로 늘어난다.

싹수가 노랗다면 없애야하듯이 가지쳐야한다.

 

 

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

 

---

 

 

 

 

#맞은 풀이

#include <bits/stdc++.h>

using namespace std;

const int MAX = 51;

int N, M; //
int node[MAX][MAX];

int ans = INT_MAX;

vector<pair<int,int>> chicken;
vector<pair<int,int>> house;
bool checked[51][51];

vector <pair<int,int>> chosen;

//idx가 있는 이유. 이미 골라본 것은 다시 고르지 않음.
void func(int cnt, int idx){
    if(cnt == M){
        //chosen에 고른 치킨집으로 모든 집들에 대해서 치킨 거리를 구함
        int cDist = 0;
        //해당 집에서 골라낸 치킨집중 치킨거리가 최솟값을 더함.
        
        //집 2N개 치킨집 M개 고름
        for(auto h : house){
            int hDist = INT_MAX;
            for(auto ch : chosen){
                int x,y;
                x = abs(ch.first - h.first);
                y = abs(ch.second - h.second);
                hDist = min(hDist, x + y);
            }
            cDist += hDist;
        }
        ans = min(ans, cDist);
        return;
    }
    //치킨집 개수
    for(int i = idx; i<chicken.size(); i++){
        auto x = chicken[i]; //치킨집의 좌표
        
        //아래 조건 정말 중요하다 -> Backtracking에서 가짓수를 줄일 수 있다 ***
        if(chicken.size()-i<M-cnt)return; //뽑아야하는 개수가 뽑을 수 있는 개수보다 많으면 종료 -> 중요
        if(checked[x.first][x.second])continue; //중복 없이 집어넣음.
        checked[x.first][x.second] = true;
        chosen.push_back(x);
        //선택
        func(cnt+1, idx+1);//진행
        //복원
        chosen.pop_back();
        checked[x.first][x.second] = false;        
    }
}


int main(){
    
    cin.tie(0);
    ios::sync_with_stdio(0);
    
    cin >> N >> M;
    
    //N^2
    for(int i=1; i<=N; i++){
        for(int j=1; j<=N; j++){
            cin >> node[i][j];
            if(node[i][j] == 1) house.push_back({i,j}); //집 좌표
            else if(node[i][j] == 2) chicken.push_back({i,j}); //치킨 집 좌표
        }
    }
    
    func(0,0);
    
    cout << ans;
    
    
    return 0;
}

 

 

백트랙킹의 핵심은 가지치기로 아래 조건 3가지가 제일 중요하다.

 

idx부터 뽑는 이유는 이미 앞에서 뽑아서 세어진 개수는 중복해서 세지 않겠다는 말이고

뽑아봤자 M개를 만들지 못한다면 해당 가지는 쳐내야하며

이미 집어넣은 치킨집을 중복으로 넣어서는 안된다는 말이다.

3가지가 다 중요하다.