[C++] 백준 15686 치킨 배달

#include <iostream>
#include <vector>
#include <algorithm>
 
int N = 0;
int M = 0;
int iMin = 214700000;
 
int graph[51][51] = {};
std::vector<std::pair<int, int>> vecHouse = {};
std::vector<std::pair<int, int>> vecChicken = {};
 
void Min()
{
    std::vector<int> vec(vecChicken.size(), 0);
 
    for (int i = 0; i < M; ++i)
    {
        vec[i] = 1;
    }
 
    do
    {
        int iSum = 0;
 
        for (int i = 0; i < vecHouse.size(); ++i)
        {
            int iCount = 100;
 
            for (int j = 0; j < vecChicken.size(); ++j)
            {
                if (vec[j])
                {
                    iCount = std::min(iCount, abs(vecChicken[j].first - vecHouse[i].first) + abs(vecChicken[j].second - vecHouse[i].second));
                }
            }
 
            iSum += iCount;
        }
 
        iMin = std::min(iMin, iSum);
 
    } while (std::prev_permutation(vec.begin(), vec.end()));
}
 
int main() 
{
    std::cin >> N >> M;
 
    for (int i = 0; i < N; ++i)
    {
        for (int j = 0; j < N; ++j)
        {
            std::cin >> graph[i][j];
 
            if (graph[i][j] == 1)
            {
                vecHouse.push_back({ i,j });
            }
 
            else if (graph[i][j] == 2)
            {
                vecChicken.push_back({ i,j });
            }
        }
    }
 
    Min();
 
    std::cout << iMin;
 
    return 0;
}

 

모든 치킨집의 위치, 집의 위치를 따로 저장해놓고 치킨집의 위치를 M개 만큼만 확인해보고 계산합니다.