[백준] 15686 치킨 배달

삼성 SW 역량테스트에 나온 문제다

비트를 통해 완전탐색을 하면 답을 구할 수 있다

치킨집과 집을 미리 vt에 따로 담아두고 

for문을 돌리며 bit가 m개 체크된다면

지금 체크된 치킨집과 집들과의 최소거리를 다 구해보면 된다!

소스코드

#include <iostream>
#include <algorithm>
#include <vector>
#include <cmath>
using namespace std;
int map[55][55], n, m,ccnt;
vector<pair<int, int>> chi, home;
 
int dist(int x1, int y1, int x2, int y2) {
    return abs(x1 - x2) + abs(y1 - y2);
}
int go(int x) {
    vector<pair<int, int>> vt;
        for (int j = 0; j < ccnt; j++) {
            if (x&(1 << j)) vt.push_back(chi[j]);
        }
    int ret = 0;
    for (int i = 0; i < home.size(); i++) {
        int d = 1e9;
        for (int j = 0; j < vt.size(); j++) {
            d = min(d, dist(home[i].first, home[i].second, vt[j].first, vt[j].second));
        }
        ret += d;
    }
    return ret;
}
int main() {
    scanf(" %d %d", &n, &m);
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            scanf(" %d", &map[i][j]);
            if (map[i][j] == 1) home.push_back({ i,j });
            else if (map[i][j] == 2) chi.push_back({ i,j });
        }
    }
    ccnt = chi.size();
    int ans = 1e9;
    for (int i = 0; i < (1 << ccnt); i++) {
        int cnt = 0;
        for (int j = 0; j < ccnt; j++) {
            if (i&(1 << j)) cnt++;
        }
        if (cnt == m) {
            ans = min(ans, go(i));
        }
    }
    printf("%d\n", ans);
    return 0;
}