BOJ 15686 - 치킨 배달

문제 링크

#include <bits/stdc++.h>
using namespace std;

typedef pair<int, int> pii;

vector<pii> house, chicken;

int bitCount(int x) {
    int ret = 0;
    while(x > 0) {
        ret += x & 1;
        x >>= 1;
    }
    return ret;
}

int d(pii p1, pii p2) {
    return abs(p1.first - p2.first) + abs(p1.second - p2.second);
}

int calculate(int mark) {
    int ret = 0;
    for(pii h : house) {
        int k = mark, idx = chicken.size() - 1, dist = 0x7fffffff;
        while(k > 0 && idx >= 0) {
            if(k & 1) dist = min(dist, d(h, chicken[idx]));
            k >>= 1;
            idx--;
        }
        ret += dist;
    }
    return ret;
}

int main() {
    ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
    int n, m, x;
    cin >> n >> m;
    for(int i = 0; i < n; ++i) {
        for(int j = 0; j < n; ++j) {
            cin >> x;
            if(x == 1) house.push_back({i, j});
            else if(x == 2) chicken.push_back({i, j});
        }
    }
    int ans = 0x7fffffff;
    int limit = 1 << chicken.size();
    for(int i = 1; i < limit; ++i) {
        if(bitCount(i) != m) continue;
        ans = min(ans, calculate(i));
    }
    cout << ans;
    return 0;
}

다른 건 그렇다 쳐도 이 긴 코드를 한번에 작성하고 아무 수정 없이 맞았다는게 너무 신기했다.

기본적으로 bitmask 를 적절히 사용하여 치킨집이 남아있으면 \(1\), 남아있지 않으면 \(0\) 으로 생각하고, 현재 존재하는 치킨집의 개수가 \(k\) 개 일때, \(1\) 부터 \(2^k - 1\) 까지 돌면서 이 중 bitCount 의 값이 \(M\) 인 경우에만 치킨거리를 계산했다.

치킨 거리 계산을 편하게 하기 위해서 집의 위치와 치킨집의 위치는 따로 vector<pii> 에 저장했다. house 의 길이의 최댓값은 \(2N\), chicken 의 길이의 최댓값은 \(13\) 이다.

시간 복잡도를 계산해 보자.

for 문은 최대 \(2^{13}\) 회 수행된다. bitCount 는 상수 시간이므로 무시하고, \({13 \choose M}\) 번만큼 calculate 가 실행된다.
calculate 의 시간 복잡도는 \(\mathcal{O}(2N\cdot 13)\) 이므로 총 \(\mathcal{O}(N\cdot {13 \choose M})\) 이다.

이성찬 / Sungchan Yi