[백준] 15686 치킨 배달

15686번: 치킨 배달

 

www.acmicpc.net

풀이

백트래킹을 사용하면 어렵지 않게 해결할 수 있다. 선택한 치킨집의 인덱스를 저장해서 치킨거리를 계산하기 쉽도록 구현했다.

코드

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

int n, m, ans = INT_MAX;
int map[50][50];
vector<int> cand;
vector<pair<int, int>> home, chicken;

void dfs(int idx, int cnt) {
    if (cnt == m) {
        int tmp = 0;
        for (int i = 0; i < home.size(); i++) {
            int min_dist = INT_MAX;
            for (int j = 0; j < cand.size(); j++)
                min_dist = min(min_dist, abs(home[i].first - chicken[cand[j]].first) + abs(home[i].second - chicken[cand[j]].second));
            tmp += min_dist;
            if (tmp > ans) return;
        }
        ans = min(ans, tmp);
        return;
    }

    for (int i = idx + 1; i < chicken.size(); i++) {
        cand.push_back(i);
        dfs(i, cnt + 1);
        cand.pop_back();
    }
}

int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);

    cin >> n >> m;
    for (int i = 0; i < n; i++)
        for (int j = 0; j < n; j++) {
            cin >> map[i][j];
            if (map[i][j] == 1) home.push_back({ j, i });
            if (map[i][j] == 2) chicken.push_back({ j, i });
        }
    dfs(-1, 0);
    cout << ans << '\n';
    return 0;
}