[알고리즘] 백준 15686

백준 15686번 치킨 배달

해결 과정 요약

치킨집들 중에 M개의 치킨집을 골라야 하므로 next_permutation함수를 이용해 조합을 만들어준다. 가장 가까운 치킨집을 구하는 cal함수를 만들어준다.
가장 가까운 치킨집을 구하기위해 bfs를 사용할 수도 있지만 치킨집의 최대 개수가 13개로 주어졌으므로 그냥 for문을 모든 치킨집에 대하여 돌리는게 더 빠르다.
do while 문을 돌면서 모든 조합 경우의 수에 대하여 치킨거리를 구해주고 그중에 가장 작은 값을 출력해준다.

풀이

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

int N,M,K;
int m[100][100];
vector<pair<int,int>> v;
vector<int> idx;
vector<int> tmp;
int ret = 987654321;

bool next(){
    return next_permutation(tmp.begin(), tmp.end());
}
int cal(int y, int x){
    int a = 987654321;
    for(int i=0; i<K; i++){
        if(!tmp[i]){
            int j = idx[i];
            a = min(a, abs(v[j].first - y) + abs(v[j].second - x));
        }
    }
    return a;
}

int main(){
    ios::sync_with_stdio(false);
    cin.tie(NULL); cout.tie(NULL);
    
    cin >> N >> M;
    for(int i=0; i<N; i++){
        for(int j=0; j<N; j++){
            cin >> m[i][j];
            if(m[i][j] == 2){
                v.push_back({i, j});
                idx.push_back(K);
                K ++;
            }
        }
    }
    for(int i=0; i<M; i++) tmp.push_back(0);
    for(int i=M; i<K; i++) tmp.push_back(1);
    
    do{
        int cur = 0;
        for(int i=0; i<N; i++){
            for(int j=0; j<N; j++){
                if(m[i][j] == 1){
                    cur += cal(i, j);
                }
            }
        }
        ret = min(ret, cur);
        
    }while(next());
    
    cout << ret;
    return 0;
}

코멘트

조합을 구현할 때 next_permutation을 이용해서 구현했는데 이 방법이 시간이 오래걸린다는 것을 알게되었다.
그냥 조합을 재귀함수로 만들어서 구하는게 더 빠르다.