백준 15686번 치킨배달 C++

문제

www.acmicpc.net/problem/15686

15686번: 치킨 배달

 

코드

#include<bits/stdc++.h>

using namespace std;

int n, m, a[52][52], ret = 987654321;
vector<vector<int>> chickenList;
vector<pair<int, int>> home, chicken;

void combi(int start, vector<int> v)
{
    if (v.size() == m)
    {
        //m = 2 라고 가정하면
        // 01 02 03 04 12 13 14 23 24 34의 경우의수 가 나온다
        // 01 => 0번째 치킨집, 1번째 치킨집
        // 02 => 0번째 치킨집, 2번째 치킨집 을 의미한다.
        chickenList.push_back(v);
        return; 
    }
    for (int i = start + 1; i < chicken.size(); i++)
    {
        v.push_back(i);
        combi(i, v);
        v.pop_back();
    }
}

int main() 
{
    ios_base::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 >> a[i][j];
            if (a[i][j] == 1)
                home.push_back({ i,j });
            if (a[i][j] == 2)
                chicken.push_back({ i,j });
        }
    }

    vector<int> v;
    combi(-1, v);
    //chickenList = 모든 치킨집을 조합하여 나올 수 있는 경우의 수
    //cList = 경우의 수 중 1가지의 경우
    for (vector<int> cList: chickenList)
    {
        int tmpRet = 0;
        for (pair<int, int> homePosition : home)
        {
            int minNum = 987654321;
            for (int ch : cList)
            {
                int y = chicken[ch].first;
                int x = chicken[ch].second;
                int dist = abs(homePosition.first - chicken[ch].first) + abs(homePosition.second - chicken[ch].second);
                minNum = min(minNum, dist);
            }
            tmpRet += minNum;
        }
        ret = min(ret, tmpRet);
    }

    cout << ret << "\n";

    return 0;
}