[백준] 15686 치킨 배달(C++)

15686번: 치킨 배달 (acmicpc.net)

15686번: 치킨 배달

---

난이도 : 골드 5

 

풀이 과정 :

각 집마다의 치킨거리를 구해 마을의 총 치킨거리가 최소가 되도록하는 문제입니다.

n이 50이므로 최대 집 개수+치킨집개수은 250이 됩니다. 

따라서 집개수와 치킨집 개수가 반반이라고 했을 때 최대 125*125 =  15625 번 연산을 하므로 

제한시간이 1초라서 완탐으로 풀 수 있는 문제 였습니다. 

 

완전탐색문제가 되면 복잡할거없이 치킨집을 조합으로 m개 고른다음,

m개마다의 치킨거리의 최솟값을 구하면 되는 문제가 되기때문에 stl이용하면 더 간단하게 풀수있는문제입니다.

 

코드 :

#include <iostream>
#include <algorithm> 
#include <vector>
using namespace std;

int n, m, arr[60][60], ans = 1e9, sum[255];
pair<int, int> h[255], c[255];
int main() {
    ios::sync_with_stdio(false);
    cin.tie(NULL), cout.tie(nullptr);
    cin >> n >> m;

    int c1 = 0, c2 = 0;
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            cin >> arr[i][j];
            if (arr[i][j] == 1) {
                h[c1].first = i;
                h[c1].second = j;
                c1++;
            }
            if (arr[i][j] == 2) {
                c[c2].first = i;
                c[c2].second = j;
                c2++;
            }
        }
    }

    vector<bool> temp(c2, true);
    for (int i = 0; i < c2 - m; i++) {
        temp[i] = false;
    }

    do {
        for (int i = 0; i < c1; i++) {
            sum[i] = 1e9;
        }
        for (int i = 0; i < c2; i++) {
            if (temp[i] == true) {
                for (int j = 0; j < c1; j++) {
                    int dx = abs(h[j].first - c[i].first);
                    int dy = abs(h[j].second - c[i].second);
                    sum[j] = min(sum[j], dx + dy);               
                }
            }
        }
        int s = 0;
        for (int i = 0; i < c1; i++) {
            s += sum[i];
        }
        ans = min(s, ans);
    } while (next_permutation(temp.begin(), temp.end()));  
    
    cout << ans;
}