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

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

15686번: 치킨 배달

/* 그 동안 코딩 업로드를 못했다. 이유를 나열하자면

1. 오프라인 강의가 3시간 강의라 한번 강의를 들으면 풀어야할 문제가 엄청 많다. 초반에는 2 ~ 3달 전에 풀었던 문제라 다소 쉽게 풀었지만 점점 안 풀었던 문제가 생기고, 또 난이도 상승으로 (일주일에 2번밖에 안가지만) 문제를 풀고 수업에 참여하기가 어려웠다.
2. spring을 따로 공부하고 있다. 그리고 node.js로 공부할 예정이다. 코딩 문제는 꾸준히 풀고 있었지만, 공부할게 많아져 시간이 부족해 업로드를 하지 않았다. */

 본 문제는 집과 치킨집의 거리를 계산하는 문제다. 문제의 조건에 보면 도시에 있는 치킨집 중에서 최대 M개를 고르고, 나머지 치킨집은 모두 폐업시켜야 한다. 라고 제시되어 있다. 문제를 풀면서 자영업이 쉬운게 아니라는 것을 다시한번 알게 해준다.

1. 입력을 받으면서 치킨집과 집을 분류한다.
2. 치킨집 중 M개를 고른다.
3. 집에서 가장 가까운 치킨집을 고른다.
4. 3번의 결과를 모두 더하여 가장 작은 치킨 거리를 구한다.

#include <cstdio>
#include <vector>
#include <cstring>
 
using namespace std;
int d[51][51];
int result[101];
int n, m, Min = 1e9;
bool chk[14];
vector<pair<int, int>> u;
vector<pair<int, int>> v;
 
int dist(int x, int y, int a, int b) {
    int tmp1 = x-a;
    if (tmp1 < 0) tmp1 = -tmp1;
    int tmp2 = y-b;
    if (tmp2 < 0) tmp2 = -tmp2;
    return tmp1 + tmp2;
}
 
void cal(int index, int cnt) {
    if (index == v.size()) {
        if (cnt == m) {
            memset(result, -1, sizeof(result));
            // 집에서 가장 가까운 치킨집 계산
            for (int i = 0; i < u.size(); i++) {
                int x = u[i].first;
                int y = u[i].second;
                int ans = 1e9;
                for (int j = 0; j < v.size(); j++) {
                    if (chk[j]) {
                        int a = v[j].first;
                        int b = v[j].second;
                        int tmp = dist(x, y, a, b);
                        if (ans > tmp) ans = tmp;
                    }
                }
                if (result[i] == -1 || result[i] > ans) result[i] = ans;
            }
            int ans = 0;
            // 가장 작은 치킨 거리 구하기
            for (int i = 0; i < u.size(); i++) {
                ans += result[i];
            }
            if (Min > ans) Min = ans;
        }
    }
    else {
        // M개의 치킨집 고르기
        chk[index] = true;
        cal(index+1, cnt+1);
        chk[index] = false;
        cal(index+1, cnt);
    }
}
 
int main() {
    scanf("%d %d", &n, &m);
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            scanf("%d", &d[i][j]);
            // 집, 치킨집 분류
            if (d[i][j] == 1) u.push_back(make_pair(i, j));
            if (d[i][j] == 2) v.push_back(make_pair(i, j));
        }
    }
    cal(0, 0);
    printf("%d\n", Min);
}