백준 15686 치킨배달

<링크>

https://www.acmicpc.net/problem/15686

<소스코드>

#include<cstdio>
#include<vector>
#include<math.h>
#include<algorithm>
using namespace std;
typedef pair<int, int> P;
vector<P> h,c,a; // 집, 치킨집, 남겨둘 치킨집
int N, M;
int ans = 1e9;
void check(vector<P> &a)
{
    if (a.size() == 0)
        return;
    int sum = 0;
    for (P i : h)
    {
        int m = 1e9;
        for (P j : a)
            m = min(m, abs(i.first - j.first) + abs(i.second - j.second));
        sum += m;
    }
    ans = min(ans, sum);
}
void recur(int i, int len)
{
    if (len <= M)
        check(a);
    if (i == c.size()||len>M)
        return;
    a.push_back(c[i]);
    recur(i + 1, len + 1);
    a.pop_back();
    recur(i + 1, len);
}
int main()
{
    scanf("%d%d", &N, &M);
    for(int i=0;i<N;++i)
        for (int j = 0; j < N; ++j)
        {
            int n;
            scanf("%d", &n);
            if (n == 1)
                h.push_back({ i,j });
            if (n == 2)
                c.push_back({ i,j });
        }
    recur(0,0);
    printf("%d", ans);
}
 

<풀이>

1. 집 좌표 리스트, 치킨집 좌표 리스트를 미리 준비해둔다.

2. 재귀함수를 이용해서 치킨집 조합을 만든다.

i번째 치킨집을 포함하면 a벡터에넣고 재귀호출, 안하면 a.pop_back()으로 뺀 후 재귀호출하고

현재까지 찍은 치킨집 개수가 M개 이하이면 check()함수에 a벡터를 던져준다.

찍은 치킨집 개수가 M개를 넘어가거나 i가 총 치킨집 개수를 넘어가면 return한다.

3. chek()함수에는 내가 찍은 치킨집들의 좌표가 넘어오기 때문에 집 하나당, 찍힌 치킨집 전부를 보며 최솟값을 찾아 더해준다.

모든 집들에 대해 반복해서 더하면 찍은 치킨집들로 만든 도시의 치킨거리가 나온다.

이 값을 보고 답을 갱신한다.