[브루트 포스 / BOJ 15686 / C++] 치킨 배달

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

15686번: 치킨 배달

1)  집, 치킨집의 좌표를 담는 배열을 선언한다.
2) 치킨집의 개수 중에 M개를 뽑아내는 조합 함수를 구성한다.
3) 뽑은 M개를 통해 도시 치킨 거리를 구한다. 이때 최종 결과값 res는 min 함수로 업데이트해준다.

이 문제는 시간 복잡도를 계산해보면 그렇게 크지 않다. 즉 완전 탐색으로 해결 가능하다!

 

복잡하게 생각할 것 없이 문제 조건 그대로 구현해주면 된다.

 

집의 좌표를 담은 배열 하나, 치킨집의 좌표를 담은 배열 하나씩 만들자. 

 

먼저, 치킨집들 중에서 M개를 뽑아야한다. 즉, 조합이다.

 

이건 재귀함수로 만들어주면 된다!

 

M개를 뽑았으면, 뽑은 M개를 이용해 미리 구해둔 집 좌표와 뽑은 M개의 치킨집들의 좌표를 비교해서 

거리들을 구하고, 그 거리들의 합을 구한다!

 

이때, 최종 결과 res는 solve함수가 돌때마다 업데이트 해주면 된다.

 

참고로 INT_MAX는 int형 수 중에 가장 큰 값을 의미한다!(2^31-1)

 

#include <bits/stdc++.h>

using namespace std;

int N, M;
int res = INT_MAX;
int bd[100][100];
vector<pair<int,int>> home, chks, select_chks;

void solve(){
    int city_chk_dis = 0;
    for(int i = 0 ; i < home.size() ; i++){ // 집 개수만큼 다 더해줘.
        int home_dis = INT_MAX;
        for(int j = 0 ; j < select_chks.size() ; j++){ // 1집당 M개 치킨집 거리들.
            int dis = abs(home[i].first-select_chks[j].first) + abs(home[i].second-select_chks[j].second);
            home_dis = min(dis, home_dis);
        }
        city_chk_dis += home_dis;
    }
        
    res = min(city_chk_dis, res);
}

void combi(int start, vector<pair<int,int>> b){
    if(b.size()==M) { // M개 뽑음.
        for(auto i : b) select_chks.push_back({i.first, i.second}); // M개 전부 select_chks에 넣기.
        solve();
        select_chks.clear(); // vector 비우기.
        return;
    }
    
    for(int i = start+1; i < chks.size(); i++){ // 0부터 넣어주기.
        b.push_back(chks[i]);
        combi(i,b);
        b.pop_back();
    }
    return;
}




int main(){
    ios::sync_with_stdio(false);
    cin.tie(NULL); cout.tie(NULL);
    
    cin >> N >> M;
    
    //(1,1)부터 (N,N)까지 저장
    for(int i = 1 ; i <= N; i++){
        for(int j = 1 ; j <= N; j++) {
            cin >> bd[i][j];
            if(bd[i][j]==1) home.push_back({i,j}); // 집
            if(bd[i][j]==2) chks.push_back({i,j}); // 치킨집
            
        }
    }
    
    vector<pair<int,int>> b;
    combi(-1, b);

    
    cout << res;
    
    return 0;
}