백준 15686번 문제 ( 치킨 배달 )

문제 출처 : https://www.acmicpc.net/problem/15686

15686번: 치킨 배달

이 문제는 가장 수익을 많이 낼 수 있는 치킨집의 개수를 구하는 것이다.

나머지 치킨집은 폐업을 시키고 집에서의 치킨 집과의 거리의 최소를 구하는 문제이다.

그래서 방문 배열과 브루트 포스를 이용하여 모든 경우를 탐색하여 값을 구할 수 있었다.

아래는 해당 문제를 해결한 소스이다. 

#include<stdio.h>
#include<math.h>
#include<algorithm>
#pragma warning(disable:4996)
using namespace std;
int arr[51][51];
int visit[51];
int route = 999999999;
struct list
{
    int x;
    int y;
};
list chicken[51];
list home[102];
int chicken_index = 0;
int home_index = 0;
void find(int start, int cnt, int M)
{
    if (cnt == M)
    {
        int value = 0;
        for (int i = 0; i < home_index; i++) //  집 
        {
            int sum = 99999998;
            for (int j = 0; j < chicken_index; j++) // 치킨 집 
            {
                if (visit[j] == 1)
                    sum = min(sum, abs(home[i].x - chicken[j].x) + abs(home[i].y - chicken[j].y));
            }
            value = value + sum;
        }
        if (value < route)
            route = value;
        return;
    }
    for (int i = start; i < chicken_index; i++)
    {
        visit[i] = 1;
        find(i + 1, cnt + 1, M);
        visit[i] = 0;
    }
    return;
}
int main()
{
    int N;
    int M;
    int num;
    scanf("%d %d", &N, &M);
    for (int i = 0; i < N; i++)
    {
        for (int j = 0; j < N; j++)
        {
            scanf("%d", &num);
            if (num == 1)
            {
                home[home_index].x = i;
                home[home_index].y = j;
                home_index++;
            }
            else if (num == 2)
            {
                chicken[chicken_index].x = i;
                chicken[chicken_index].y = j;
                chicken_index++;
            }
        }
    }
    find(0, 0, M);
    printf("%d", route);
}