[백준/c++] 15686번: 치킨 배달

 

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

15686번: 치킨 배달

 

처음 문제를 풀 땐 BFS과 Backtracking으로 할 생각이었다. 정작 풀어보니까 시간 초과가 발생했는데

생각해보니 BFS를 하지 않고 치킨집과의 거리를 절댓값으로 구하면 되는 것이었다..!ㅠ

그래서 Backtracking으로 짜서 경우의 수에 대해서

다시 했지만 또 시간초과가 발생해서 뭐지... 어떻게 해야 되는 건가 싶어서 다른 사람의 코드를 봤다.

경우의 수를 2진수로 구성했다.

next_permutation 함수를 사용해서 수열을 값을 차례대로 바꿔줬다.

 

 

이 문제에서 얻은 건 경우의 수를 2진수로 구성하는 것이다. 꼭 기억하고 있어야겠다.

 

#include <iostream>
#include <queue>
#include <vector>
#include <algorithm>
#include <numeric>
using namespace std;

int arr[51][51];
vector<pair<int, int>> chicken;
vector<pair<int, int>> house;
bool visit[13];
int n, m;

int main(){
    ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    cin >> n >> m;
    for(int i=0; i<n; i++) { // O(n^2)
        for(int j=0; j<n; j++){
            cin >> arr[i][j];
            if(arr[i][j] == 1)      house.push_back({i, j});
            if(arr[i][j] == 2) chicken.push_back({i, j});
        }
    }
    vector<int> permutation(chicken.size(), 1); //치킨집 개수만큼 1으로 채움
    fill(permutation.begin(), permutation.begin() + chicken.size() - m, 0); //2진수로 만든 치킨집 선택 경우의 수
    int sum = 100000000;
    do{
        int s = 0;
        for(auto h:house){ //집(1)에서 가장 가까운 치킨집과의 거리 구하기(s)
            int chickenDist = 100000000;
            for(int i=0; i<chicken.size(); i++){
                if(permutation[i] == 0) continue;
                chickenDist = min(chickenDist, abs(chicken[i].first - h.first) + abs(chicken[i].second - h.second));
            }
            s += chickenDist;
        }
        sum = min(s, sum); //최소 sum(치킨 거리) 구하기
    }while(next_permutation(permutation.begin(), permutation.end()));
    
    cout << sum << '\n';
    return 0;
}