(백준 c++)15686 치킨 배달

www.acmicpc.net/problem/15686

15686번: 치킨 배달

 

이 문제의 핵심 변수는 

치킨집의 좌표를 저장하는 벡터 chicken,

집의 좌표를 저장하는 벡터 house,

조합을 구하기 위한 벡터 ind 다.

 

처음 board벡터에 집과 치킨집의 정보를 받아온다.

만약 board[i][j] == 1이면 house 벡터에,

board[i][j] == 2 이면 chicken 벡터에 좌표를 저장한다.

 

이후 ind 벡터를 선언하여 M개의 1과 chicken.size() - M 개의 0을 삽입한 후 오름차순 정렬.

ind 벡터를 가지고 next_permutation() 함수를 이용해 조합을 구한다.

 

do ~ while문 내부에서는 치킨집과 집의 거리를 구하여 최소값을 추출하면 된다.

#include <iostream>
#include <vector>
#include <algorithm>
#include <climits>

using namespace std;

int N;
int M;
int ans = INT_MAX;
vector<vector<int>> board(51, vector<int>(51, 0));
vector<pair<int, int>> chicken;
vector<pair<int, int>> house;

int main(void){
    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> ind(M, 1);

    for(int i = M; i < chicken.size(); i++){
        ind.push_back(0);
    }

    sort(ind.begin(), ind.end());
    

    do{
        int sum = 0;

        for(int i = 0; i < house.size(); i++){
            int tmp = INT_MAX;

            for(int j = 0; j < ind.size(); j++){
                if(ind[j]){
                    tmp = tmp < abs(house[i].first - chicken[j].first) + abs(house[i].second - chicken[j].second) ? tmp : abs(house[i].first - chicken[j].first) + abs(house[i].second - chicken[j].second);
                }
            }
            sum += tmp;
        }

        ans = ans < sum ? ans : sum;
    }while(next_permutation(ind.begin(), ind.end()));

    cout << ans;

    return 0;
}