[C/C++] BOJ 15686번 : 치킨 배달

1. 문제

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

2. 풀이

치킨집마다 가장 가까운 집과의 거리와, 개수를 저장한다.
여기서 개수는 거리가 1인 집이 5개 있을 경우 개수에 5가 저장된다.
치킨집 중 거리가 가장 먼 것부터 치킨집이 M개만 남게 폐업시킨다.
만약, 거리가 동일한 치킨집이 있다면 그 중 개수가 큰 것을 택한다.
그 후 다시 도시의 치킨 거리를 구해 답을 도출한다.

처음에는 위의 풀이법을 생각했다.
하지만 예제입력3이 반례였고 치킨집 본연의 거리보다는 전체적인 그림이 중요하다는 사실을 깨달았다.
아래는 위의 잘못된 풀이법으로 푼 코드이다.

//BOJ_15686 치킨 배달 [골드 5]
//예제입력 3번이 반례 -> 이렇게 풀면 안 되는구나
#include <bits/stdc++.h>
#include <iostream>
#include <queue>
#include <cmath>
#include <map>

using namespace std;
struct vnode {
    int dist, cnt;
    int r, c;
};
vector<vnode> v;
vector<pair<int, int>> zip;  //집
vector<pair<int, int>> chk;  //치킨집
pair<int, int> dist(int r, int c) {
    int ret = 1e9;
    vector<int> tmp;
    for (int i = 0; i < zip.size(); i++) {
        tmp.push_back(abs(zip[i].first - r) + abs(zip[i].second - c));
        ret = min(ret, tmp[tmp.size() - 1]);
    }

    int cnt = 0;
    for (int i = 0; i < tmp.size(); i++) {
        if (ret == tmp[i]) cnt++;
    }

    return {ret, cnt};
}

int dist2(int r, int c) {
    int ret = 1e9;
    for (int i = 0; i < v.size(); i++) {
        int tmp = abs(v[i].r - r) + abs(v[i].c - c);
        ret = min(ret, tmp);
    }
    return ret;
}

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

    int N, M; cin >> N >> M;
    for (int i = 1; i <= N; i++) {
        for (int j = 1; j <= N; j++) {
            int tmp; cin >> tmp;
            if  (tmp == 1) zip.push_back({i, j});
            else if  (tmp == 2) chk.push_back({i, j});
        }
    }
    for (int i = 0; i < chk.size(); i++) {
        pair<int, int> tmp = dist(chk[i].first, chk[i].second);
        v.push_back({tmp.first, tmp.second, chk[i].first, chk[i].second});
    }
    sort(v.begin(), v.end(), [](const vnode &a, const vnode &b) {
        if (a.dist == b.dist)
            return a.cnt >= b.cnt;  // dist가 동일하면 cnt로 정렬
        return a.dist <= b.dist;  // 그렇지 않으면 dist로 정렬
    });
    for (int i = v.size() - 1; i >= M; i--) {
        v.erase(v.begin() + i);
    }
    int sum = 0;
    for (int i = 0; i < zip.size(); i++) {
        sum += dist2(zip[i].first, zip[i].second);
    }

    cout << sum << '\n';
}

개인의 최적이 전체가 되지 않는다는 걸 깨달았으니 풀이를 다시 생각해보자.

치킨집의 개수 K개 중에 폐업시키지 않을 M개를 고른다.(KCM 조합 이용)
고른 M개에 대해서만 도시의 치킨 거리를 구한다.
그 중 가장 작은 도시의 치킨 거리가 답이다.

꽤나 간단하고 직관적인 풀이를 복잡하게 생각했던 것 같다.
이 문제 풀면서 nCm 조합 원소 리스트 구하는 것을 복습하는 기회가 되었다.

3. 코드

//BOJ_15686 치킨 배달 [골드 5]
#include <bits/stdc++.h>
#include <iostream>
#include <queue>
#include <cmath>
#include <map>

using namespace std;

vector<pair<int, int>> zip;  //집
vector<pair<int, int>> chk;  //치킨집
vector<int> nchk;    //남은 치킨집 인덱스

void Combinations(int S, int R, int N, vector<vector<int>>& res, vector<int>& cur) {
    if (R == 0) {
        res.push_back(cur);
        return;
    }

    for (int i = S; i < N; i++) {
        cur.push_back(i);
        Combinations(i + 1, R - 1, N, res, cur);
        cur.pop_back();
    }
}
vector<vector<int>> nCm(int N, int M) {
    vector<vector<int>> res;
    vector<int> cur;
    Combinations(0, M, N, res, cur);
    return res;
}

int dist(int r, int c) {
    int ret = 1e9;
    for (int i = 0; i < nchk.size(); i++) {
        int tmp = abs(chk[nchk[i]].first - r) + abs(chk[nchk[i]].second - c);
        ret = min(ret, tmp);
    }
    return ret;
}

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

    int N, M; cin >> N >> M;
    for (int i = 1; i <= N; i++) {
        for (int j = 1; j <= N; j++) {
            int tmp; cin >> tmp;
            if  (tmp == 1) zip.push_back({i, j});
            else if  (tmp == 2) chk.push_back({i, j});
        }
    }
    vector<vector<int>> Comb = nCm(chk.size(), M);

    int ans = 1e9;
    for (int i = 0; i < Comb.size(); i++) {
        nchk.clear();
        for (int j = 0; j < Comb[i].size(); j++) {
            nchk.push_back(Comb[i][j]);
        }
        int sum = 0;
        for (int i = 0; i < zip.size(); i++) {
            sum += dist(zip[i].first, zip[i].second);
        }
        ans = min(ans, sum);
    }

    cout << ans << '\n';
}