[15686번] 치킨 배달

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

15686번: 치킨 배달

문제접근법

1. 치킨 집의 위치와 가정 집의 위치를 담을 자료 구조가 필요하다. 치킨 집의 위치와 가정 집의 위치를 통해서 도시의 치킨 거리를 구할 수 있기 때문이다.

 

2. 최대 M개를 뽑으라고 했으니, 조합이 필요하다. 조합을 통해서, 1 ~ M개까지 뽑은 다음에 도시의 치킨 거리를 확인해주면 된다.

 

유의사항

특별히 문제의 유의 사항이 보이지 않는다.

 

해설코드

#include <iostream>
#include <cstring>
#include <algorithm>
#include <vector>
using namespace std;
 
int N, M;
vector<pair<int, int>> h_v;
vector<pair<int, int>> c_v;
int val;
int sol[13];
int answer = -1;
 
void backtracking(int cnt, int idx, int m) {
    if (cnt == m) {
        int result = 0;
        for (int i = 0; i < h_v.size(); i++) {
            int h_r = h_v.at(i).first;
            int h_c = h_v.at(i).second;
            int tmp = 51 * 51;
            for (int j = 0; j < cnt; j++) {
                int c_r = c_v.at(sol[j]).first;
                int c_c = c_v.at(sol[j]).second;
                tmp = min(tmp, abs(h_r - c_r) + abs(h_c - c_c));
            }
            result += tmp;
        }
 
        if (answer == -1)
            answer = result;
        else
            answer = min(answer, result);
 
        return;
    }
 
    if (idx == c_v.size()) {
        return;
    }
 
    sol[cnt] = idx;
    backtracking(cnt + 1, idx + 1, m);
    backtracking(cnt, idx + 1, m);
 
    return;
}
 
int main(void) {
    //freopen("input.txt", "r", stdin);
    cin >> N >> M;
    for (int i = 1; i <= N; i++) {
        for (int j = 1; j <= N; j++) {
            cin >> val;
            if (val == 1) {
                h_v.push_back(make_pair(i, j));
            }
            else if (val == 2) {
                c_v.push_back(make_pair(i, j));
            }
        }
    }
 
    // Backtracking
    for (int i = M; i >= 1; i--) {
        backtracking(0, 0, i);
    }
 
    cout << answer << endl;
    return 0;
}