[백준] 15686번 치킨배달 C++

문제

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

브루트 포스 문제...시간복잡도 때메 가져왔다.

---

 

풀이

1. 백트래킹으로 모든 치킨집 경우의 수를 조합으로 구하기

2. 구한 조합과 집 사이 거리를 모두계산해서 최소값 구하기 

 

시간복잡도 :

최대 경우의수 : 17C7 = 1716 대충 2000

최대 집수 : 100

비교수 : 100 * 7 = 700

700 * 2000 = 1400000

통과는하지만 그렇게 빠르진 않다.

---

#include <bits/stdc++.h>

using namespace std;
#define X first
#define Y second
#define INF 1e9;
int N,M;
int answer = INF;
vector <pair<int,int>> chicken;
vector <pair<int,int>> chicken_temp;
vector <pair<int,int>> house;


void check_min(){
    int temp_sum = 0;
    for (int i = 0; i < house.size(); ++i) {
        int temp_dis = INF;
        for (int j = 0; j < chicken_temp.size(); ++j) {
            temp_dis = min(temp_dis, abs(house[i].X - chicken_temp[j].X) + abs(house[i].Y - chicken_temp[j].Y));

        }
        temp_sum += temp_dis;
    }
    answer= min(temp_sum, answer);
}

void DFS(int cnt, int x){
    if(cnt == M) {
        check_min();
        return;
    }

    for (int i = x; i < chicken.size()-(M-cnt-1); ++i) {
        chicken_temp.push_back({chicken[i]});
        DFS(cnt + 1, i + 1);
        chicken_temp.pop_back();
    }


}

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