백준(boj)15686 - 치킨 배달

문제 링크 - https://www.acmicpc.net/problem/15686

👀문제이해 및 풀이방법

브루트 포스 문제이다. 모든 집에 대해 일정 치킨집을 조합방식으로 뽑아 bfs를 돌려서 뽑았는데
그냥 뽑은 치킨집들을 하나하나 비교해보는게 빨랐다..
조합을 사용하는 방법은 algorithm라이브러리의 next_permutation함수를 사용하는데 조합에 사용될 배열의 크기와 같은 크기의배열을 만들고 뽑고싶은 조합의 수를 1로 넣어 permutation을 돌리고 1이 있는 위치만을 파악하여 조합에 사용될 배열에서 원소들을 뽑아내면 조합이 완성이 된다
조합을 통해 치킨집들을 뽑아내고 뽑아낸 치킨집들과 집의 거리중 가장 가까운 치킨집의 거리를 더해주면 되는 문제였다

📝코드

#include <iostream>
#include <vector>
#include <queue>
#include <algorithm>
using namespace std;
int INF =2000000000;
int dx[4]={1,0,-1,0};
int dy[4]={0,1,0,-1};
struct _node{
    int x,y,degree;
};
class chicken{
private:
    vector<pair<int,int>> home,ck;
    int N,M;
public:
    chicken(){
        std::cin >> N >> M;
        set_val();
    }
    void set_val(){
        int tmp;
        for(int i=0;i<N;i++){
            for(int j=0;j<N;j++){
                std::cin >> tmp;
                if(tmp==1)
                    home.push_back({i,j});
                else if(tmp==2)
                    ck.push_back({i,j});
            }
        }
    }
    int find_dis(vector<int>& combination){
        int dis=0,tmp;
        for(int i=0;i<home.size();i++){
            tmp=INF;
            for(int j=0;j<ck.size();j++){
                if(combination[j])
                    tmp=min(tmp,abs(home[i].first-ck[j].first)+abs(home[i].second-ck[j].second));
            }
            dis+=tmp;
        }
        
        return dis;
    }

    void find_sol(){
        int sol= INF;
        vector<int> combination(ck.size(),0);
        for(int i=1;i<=M;i++)
            combination[ck.size()-i]=1;
        do{
            sol = min(sol,find_dis(combination));
        
        }while(next_permutation(combination.begin(),combination.end()));
        std::cout << sol << '\n';
    }

};
int main(){
    cout.tie(NULL);cin.tie(NULL);
    ios_base::sync_with_stdio(false);
    chicken ck;
    ck.find_sol();

    return 0;
}