치킨 배달

일단 이문제 예제를 보면서 무슨말인지 계속봄.

일단 최대 M중에서 "도시의 치킨 거리"를 구하는 문제이다.

"도시의 치킨 거리"는 "최소 치킨 거리"의 합이다.

즉 Board에 치킨집에 5개있고 M이 2라면은

5개중에 "최소 치킨 거리"의 합을 구하는 문제이다.

여기에서 생각난게 "조합/순열"이다.

5개의 치킨집 중에 2개를 뽑을 때 순서는 상관없기 때문에 "조합"을 사용해야한다.

즉 A, B, C, D, E라는 치킨집 있을 때

(A, B), (A, C), (A, D) ... 중에서 어떤 조합이 "최소 치킨 거리"인지 구하면 되는거같다.

그래서 먼저 조합을 구현한다음에 해당 조합을 Go함수에 넣어주는 식으로 일단 계획을 해본다.

그리고 모든 경우의 수를 Go하는 함수에 다 넣어서 최소값을 vector에 담고 sort한뒤 0번째 IDX출력하면 끝!

무식하게 풀자 ❗

얼핏보면은 2500C13인거같은데 아니다. 조건이 있기 때문에

13Cn * 100 정도 된다.

http://boj.kr/2f408212882d4bdfafd47eb68eec3f33

cpp 코드

이해를 할려고 출력하는 부분 넣어놔서 이대로 제출하면 안되고 제출할려면 출력하는 부분 지워야됨.

#include <iostream>
#include <cstring>
#include <stack>
#include <vector>
#include <map>
#include <algorithm>
using namespace std;
#define endl "\n"
const int INF = 987654321;

int n, m, Board[54][54], TempBoard[54][54];
vector<pair<int, int>> ChickenLocations;
vector<pair<int, int>> TempLocations;
vector<int> Vaules;
vector<int> Ret;

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

void SetTempBoard(const int B[54][54], const vector<pair<int, int>>& V)
{
    memset(TempBoard, 0, sizeof(TempBoard));
    for (int y = 1; y <= n; ++y)
    {
        for (int x = 1; x <= n; ++x)
        {
            if (B[y][x] == 2)
            {
                for (pair<int, int> p : V)
                {
                    if (y == p.first && x == p.second)
                    {
                        TempBoard[y][x] = 2;
                    }
                }
            }
            else
            {
                TempBoard[y][x] = Board[y][x];
            }
        }
    }
}

void Go(int y, int x, const vector<pair<int, int>>& Locations)
{
    // 기저 사례
    if (y == n + 1)
    {
        cout << "End!" << endl;
        int ret2 = 0;
        for (int i = 0; i < Vaules.size(); ++i)
        {
            ret2 += Vaules[i];
        }
        Vaules.clear();
        cout << "최소값 : " << ret2 << endl;
        cout << "############################" << endl;
        Ret.push_back(ret2);
        return;
    }

    if (x == n + 1)
    {
        Go(y + 1, 1, Locations);
        return;
    }
    if (TempBoard[y][x] == 0)
    {
        Go(y, x + 1, Locations);
        return;
    }
    if (TempBoard[y][x] == 2)
    {
        Go(y, x + 1, Locations);
        return;
    }
    if (TempBoard[y][x] == 1)
    {
        int v = INF;
        for (pair<int, int> p : Locations)
        {
            v = min(v, Dis(y, x, p.first, p.second));
        }
        cout << y << ", " << x << "에서 최소 치킨 거리 : " << v << endl;
        Vaules.push_back(v);
        Go(y, x + 1, Locations);
        return;
    }

    return;
}

void Print(const vector<pair<int, int>>& Location) 
{
    cout << "시도할 치킨 집 좌표 : " << " ";
    for (pair<int, int> pos : Location)
    {
        cout << pos.first << ", " << pos.second << " " << " ";
    }
}
void Combi(int start, vector<pair<int ,int>> Temp)
{
    if (Temp.size() == m)
    {
        Print(Temp);
        cout << endl;
        SetTempBoard(Board, Temp);

        // ######### Test ############
        for (int y = 1; y <= n; ++y)
        {
            for (int x = 1; x <= n; ++x)
            {
                cout << TempBoard[y][x] << " ";
            }
            cout << endl;
        }
        // ######### Test ############

        Go(1, 1, Temp);
        cout << endl;
        return;
    }
    for (int i = start + 1; i < ChickenLocations.size(); ++i)
    {
        TempLocations.push_back({ ChickenLocations[i].first, ChickenLocations[i].second });
        Combi(i, TempLocations);
        TempLocations.pop_back();
    }
}

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    cin >> n >> m;
    for (int y = 1; y <= n; ++y)
    {
        for (int x = 1; x <= n; ++x)
        {
            cin >> Board[y][x];
            if (Board[y][x] == 2) ChickenLocations.push_back({y, x});
        }
    }

    Combi(-1, ChickenLocations);
    sort(Ret.begin(), Ret.end());
    cout << "최종 도시 치킨 거리 최소값 : " << Ret[0];
    cout << Ret[0];
    return 0;
}