치킨 배달 / 15686번 백준

문제 분석

난이도 : 골드 5

문제 : 백 트래킹, 브루트 포스, 구현, 시뮬레이션

깨달은 점

1. unordered_set이나, set 쓰지 말고 그냥 Selected[13]으로 해야 erase 하는데에 O(1)이 된다.
 2. 인자 값으로 선택된 것의 인덱스를 넘겨줘서 그 이후만 하도록 해서 시간 복잡도를 줄인다.

 

문제 코드

#include <iostream>
#include <vector>
#include <utility>
#include <cmath>
#include <queue>
#include <algorithm>
#include <deque>
#include <set>
#include <map>
#include <unordered_map>
#include <string>
#include <unordered_set>
#include <climits>
using namespace std;

int n, m;
long long int MinimumCityChickenDistance = INT_MAX;

vector<vector<int>> City;
vector<int> HomePos;
vector<int> ChickenStorePos;
vector<int> ChickenList;
bool Selected[13];

//Initialize STD IN & OUTPUT
void Init() 
{
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
}

void CheckChickenDistance()
{
    long long int CityMinDist = 0;
    for (int Home : HomePos)
    {
        long long int ChickenMinDist = INT_MAX;
        for (int Store : ChickenList)
        {
            long long int CurDist = 
                abs(Store / 50 - Home / 50) + abs(Store % 50 - Home % 50);
            
            ChickenMinDist = min(ChickenMinDist, CurDist);
        }
        CityMinDist += ChickenMinDist;
    }
    MinimumCityChickenDistance = min(MinimumCityChickenDistance, CityMinDist);
}
void Simulate(int x, int SelectedCount)
{
    if (SelectedCount == m)
    {
        CheckChickenDistance();
    }
    else
    {
        for (int i = x; i < ChickenStorePos.size(); ++i)
        {
            if (Selected[i] == true) continue;
            ChickenList.push_back(ChickenStorePos[i]);
            Selected[i] = true;
            Simulate(i, SelectedCount + 1);
            Selected[i] = false;
            ChickenList.pop_back();
        }
    }
}

int main()
{
    Init();
    cin >> n >> m;
    
    for (int i = 0; i < n; ++i)
    {
        vector<int> Line;
        for (int j = 0; j < n; ++j)
        {
            int Tmp;
            cin >> Tmp;
            Line.push_back(Tmp);
            if (Tmp == 2)
            {
                ChickenStorePos.push_back(i * 50 + j);
            }
            else if (Tmp == 1)
            {
                HomePos.push_back(i * 50 + j);
            }
        }
        City.push_back(Line);
    }
    Simulate(0, 0);
    
    cout << MinimumCityChickenDistance;
}