백준 15686. 치킨 배달 (구현)

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

15686번: 치킨 배달

현재 있는 치킨집에서 m개의 치킨집을 골랐을 때, 나올 수 잇는 도시의 치킨 거리의 최솟값을 고른다. 따라서, 조합을 사용한다. (next_permutation함수 이용)

 

1. 특징

1) 조합: 5개중 3개를 고르는 조합을 만들고 싶으면 int mask[5] = {0, 0, 0, 1, 1}을 만든다.

2) 구현 

 

2. 코드

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


int n, m;
int board[52][52];
vector<pair<int, int>> _chvec;
vector<pair<int, int>> _hovec;
int dist[102]; //각 집에서 치킨 까지 거리 최소 배열
int ans[2000]; //조합별 최솟값을 저장하는 배열
int main(void)
{
    ios::sync_with_stdio(0);
    cin.tie(0);
    
    cin >> n >> m; //50, 13

    for(int i = 0; i < n; i++)
    {
        for(int j = 0; j < n; j++)
        {
            int x;
            cin >> x;
            board[i][j] = x;
            if(x == 1) { _hovec.push_back(make_pair(i, j));} //집이면 
            if(x == 2) { _chvec.push_back(make_pair(i, j));} //치킨집이면 
        }
    }    
    
    fill(dist, dist + 101, INT_MAX);

    int chsize = _chvec.size();
    int hosize = _hovec.size();
    vector<int> mask;//chsize에서 m개를 뽑을 때
    for(int i = 0; i < m; i++)
    {
        mask.push_back(0);
    }
    for(int i = 0; i < chsize - m; i++)
    {
        mask.push_back(1);
    }
    int cnt = 0;
    do
    {
        fill(dist, dist + 101, INT_MAX);
        for(int i = 0; i < chsize; i++)
        {
            if(mask[i] == 0) // 해당 치킨집과 집들사이 거리 구하기
            {
                
                int curchix = _chvec[i].first; // 현재 치킨집의 x값
                int curchiy = _chvec[i].second; // y값
                
                for(int j = 0; j < hosize; j++)
                {   
                    int disx = abs(curchix - _hovec[j].first);
                    int disy = abs(curchiy - _hovec[j].second);

                    int dis = disx + disy;
                  
                    dist[j] = min(dist[j], dis);
                }
            }
        }


        for(int a = 0; a < hosize; a++)
        {
            if(dist[a] != INT_MAX)
                ans[cnt] += dist[a];
        }
        cnt++;

    }while (next_permutation(mask.begin(), mask.end()));

    int answer = INT_MAX;
    for(int i = 0; i < cnt; i++)
    {
        answer = min(answer, ans[i]);
    }

    cout << answer;



}