[C언어] 25686 치킨 배달.

M개를 선택 후, BFS로 최단거리 갱신해주면 됨!!

#include <stdio.h>
#include <string.h>
 
typedef struct
{
    int y, x;
}point;
 
int map[55][55];
 
point Res[13];
int Res_visit[13];
 
point House[13];
int House_visit[13];
 
int N, M, Res_count, House_count, MIN;
 
int dx[] = { 0,0,-1,1 };
int dy[] = { -1,1,0,0 };
 
int abs(int a, int b)
{
    return a - b < 0 ? b - a : a - b;
}
 
void DFS(int Cur, int m)
{
    if(m == M)
    {
        int Chicken_Road = 0;
        int Chicken_map[55][55];
        for(int a = 0; a < 54; a++)
        {
            for (int b = 0; b < 54; b++)
            {
                Chicken_map[a][b] = 987654321;
            }
        }
        for (int i = 0; i < Res_count; i++)
        {
            if (Res_visit[i] == 1)
            {
                int visit[55][55] = {0, };
                point Q[50 * 50] = { 0, };
                int Q_Front = -1, Q_Back = -1, Road = 0;
                Q[++Q_Back].y = Res[i].y;
                Q[Q_Back].x = Res[i].x;
 
                while (Q_Front != Q_Back)
                {
                    int x = Q[++Q_Front].x;
                    int y = Q[Q_Front].y;
                    for (int D = 0; D < 4; D++)
                    {
                        int xx = x + dx[D];
                        int yy = y + dy[D];
 
                        if ((map[yy][xx] == 0 || map[yy][xx] == 1 || map[yy][xx] == 2)&& visit[yy][xx] == 0)
                        {
                            visit[yy][xx] = -1;
                            Q[++Q_Back].y = yy;
                            Q[Q_Back].x = xx;
                            if (map[yy][xx] == 1)
                            {
                                Road = (abs(yy, Res[i].y) + abs(xx, Res[i].x));
                                if (Chicken_map[yy][xx] > Road)
                                    Chicken_map[yy][xx] = Road;
                            }
                        }
                    }
                }
            }
        }
        int total = 0;
        for (int a = 1; a <= N; a++)
        {
            for (int b = 1; b <= N; b++)
            {
                if (Chicken_map[a][b] != 987654321)
                {
                    total += Chicken_map[a][b];
                }
            }
        }
        if (total < MIN)
        {
            MIN = total;
        }
        return;
    }
 
    for (int i = Cur + 1; i < Res_count; i++)
    {
        Res_visit[i] = 1;
        DFS(i, m + 1);
        Res_visit[i] = 0;
    }
    return;
}
 
int main()
{
    scanf("%d %d", &N, &M);
    memset(map, -1, sizeof(map));
    MIN = 987654321;
    for (int a = 1; a <= N; a++)
    {
        for (int b = 1; b <= N; b++)
        {
            scanf("%d", &map[a][b]);
            if (map[a][b] == 2)
            {
                Res[Res_count].y = a;
                Res[Res_count].x = b;
                Res_count++;
            }
        }
    }
 
    for (int i = 0; i < Res_count; i++)
    {
        Res_visit[i] = 1;
        DFS(i, 1);
        Res_visit[i] = 0;
    }
 
    printf("%d\n",MIN);
 
    return 0;
}