백준 15686 - 치킨 배달 / C++

[문제]

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

15686번: 치킨 배달

 

[풀이]

C++ next permutation 이용(조합), 시뮬레이션

 

[코드]

#include <bits/stdc++.h>

using namespace std;

#define X first
#define Y second

int board[55][55];
int n,m;

vector<pair<int,int>> chicken;
vector<pair<int,int>> house;

int main(void)
{
    ios::sync_with_stdio(0);
    cin.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});
            if(board[i][j] == 2) chicken.push_back({i,j});
        }
    }
    
    vector<int> brute(chicken.size(), 1);
    fill(brute.begin(), brute.begin() + chicken.size() - m, 0);
    int mn = 1000000;
    do{
        int dist = 0;
        for(auto h : house){
            int tmp = 1000000;
            for(int i=0; i<chicken.size(); i++){
                if(brute[i] == 0) continue;
                tmp = min(tmp, abs(chicken[i].X - h.X) + abs(chicken[i].Y - h.Y));
            }
            dist+=tmp;
        }
        mn = min(mn, dist);
    }while(next_permutation(brute.begin(), brute.end()));
    cout << mn;
}