치킨 배달

코드

#include <iostream> 
#include <algorithm> 
#include <vector> 
#include <deque>
#include <map>
#include <cmath>
#include <numeric>
#define INF 1e9
using namespace std;
int N, M, ans=INF;
int board[52][52];
vector<pair<int,int>> chicken;
vector<pair<int,int>> house;
int main(){
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);

    cin >> N >> M;
    for(int i=0;i<N;i++)
        for(int j=0;j<N;j++)
        {
            cin >> board[i][j];
            if(board[i][j] == 1)
                house.push_back({i,j});
            else if(board[i][j] == 2)
                chicken.push_back({i,j});
        }
    vector<int> ch(chicken.size());
    fill(ch.begin(), ch.end(), 1);
    for(int i=0;i<M;i++) ch[i] = 0;

    do{
        vector<pair<int,int>> cur_chicken;
        for(int i=0;i<ch.size();i++){
            if(ch[i] == 0) cur_chicken.push_back(chicken[i]);
        }
        /* 선택된 치킨집과 모든 집 사이의 치킨거리 최소값을 구함 */
        vector<int> tmp(house.size());
        for(int i=0;i<house.size();i++)
        {
            int val=INF;
            for(int j=0;j<cur_chicken.size();j++)
            {
                int dist = abs(house[i].first - cur_chicken[j].first) +
                            abs(house[i].second - cur_chicken[j].second);
                val = min(val, dist);
            }
            tmp[i] = val;
        }
        int sum = accumulate(tmp.begin(), tmp.end(), 0);
        ans = min(ans,sum);
    }while(next_permutation(ch.begin(), ch.end()));
    cout << ans;
    return 0;
}

• 로직
  • 총 치킨집의 개수 중 M개를 뽑는 조합으로 치킨집을 고름
  • 치킨집과 집간의 치킨거리를 구해서 최소값을 찾음