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

작성일 | In
골드 V 골드 V

문제

치킨 배달
조금 어려운 브루트포스 + 구현 문제입니다.

풀이

맵 전체를 저장하는 것이 아니라 집, 그리고 치킨집의 위치만 저장해도 됩니다.
집과 치킨집 사이의 거리는 $O(1)$에 구할 수 있기 때문에 치킨집을 $M$개로 골라내는 작업만 잘 해주면 됩니다.

다들 백트래킹으로 구현하시던데, 저는 비트마스킹을 통한 조합으로 구현했습니다.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
#include <bits/stdc++.h>
using namespace std;


int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int n, m;
    cin >> n >> m;

    vector<pair<int, int>> houses;
    vector<pair<int, int>> chicken_stores;
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            int room;
            cin >> room;

            if (room == 1) houses.push_back({i, j});
            if (room == 2) chicken_stores.push_back({i, j});
        }
    }

    int min_city_chicken_dist = INT_MAX;
    for (int k = 1; k < 1 << chicken_stores.size(); k++) {
        int chicken_count = 0;
        for (int i = 0; i < chicken_stores.size(); i++) {
            if (k & 1 << i) chicken_count++;
        }
        if (chicken_count != m) continue;

        vector<pair<int, int>> available_chicken;
        for (int i = 0; i < chicken_stores.size(); i++) {
            if (k & 1 << i) available_chicken.push_back(chicken_stores[i]);
        }

        int city_chicken_dist = 0;
        for (auto house : houses) {
            int chicken_dist = INT_MAX;
            for (auto chick : available_chicken) {
                chicken_dist = min(abs(chick.first - house.first) + abs(chick.second - house.second), chicken_dist);
            }
            city_chicken_dist += chicken_dist;
        }
        min_city_chicken_dist = min(city_chicken_dist, min_city_chicken_dist);
    }
    cout << min_city_chicken_dist;

    return 0;
}

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