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

<조건 분석>

 

1. N은 50. 집의 갯수 최대 2500개 치킨집의 개수는 13개. 13C6(치킨집 고르는 경우의 수) * (100*100)(집에서 치킨집 가는 탐색) * 6개 라고 해도 1억회는 안넘고, 1초까지는 안걸림.

 

<문제 해결 포인트>

 

1. 최대 M개를 고르라니까 조합을 써야되겠다 ! 하는 사고방식이 일어나야 함.

2. 그리고는 완전탐색으로 일일히 거리 계산해주면서 최소값 구하면 됨.

 

#include <bits/stdc++.h>
using namespace std;
using pii = pair<int, int>;

int N, M;
int board[51][51];
int visited[14];
vector<pii> cv;
vector<pii> hv;
vector<int> indexv;
int res = 987654321;

int cal(int y1, int x1, int y2, int x2)
{
    return abs(y1 - y2) + abs(x1 - x2);
}


void combi(int index)
{
    if (index == M)
    {
        int sum = 0;
        for (auto item : hv)
        {
            int temp = 987654321;
            for (auto index : indexv)
            {
                temp = min(temp, cal(cv[index].first, cv[index].second, item.first, item.second));
            }
            sum += temp;
        }

        res = min(sum, res);

        return;
    }


    for (int i = 0; i < cv.size(); i++)
    {
        if (visited[i]) continue;
        visited[i] = 1;
        indexv.push_back(i);
        combi(index + 1);
        indexv.pop_back();
        visited[i] = 0;
    }

    return ;
}

int main()
{
    ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);

    cin >> N >> M;

    for (int i = 0; i < N; i++)
    {
        for (int j = 0; j < N; j++)
        {
            cin >> board[i][j];
            if (board[i][j] == 1)
            {
                hv.push_back({i, j});
            }
            else if (board[i][j] == 2)
            {
                cv.push_back({i, j});
            }
        }
    }

    combi(0);



    cout << res;

    return 0;
}