[C언어] 15686. 치킨배달

DFS후, BFS로 치킨 거리를 구해줬는데...시간이 너무 오래걸려서!! 수정을 좀 해보았다.

우리는 집들의 위치를 입력 받으면서 알 수 있기 때문에 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[111];
int House_visit[111];
 
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_map[55][55] = { 0, };
 
        for (int i = 0; i < 55; i++)
        {
            for (int j = 0; j < 55; j++)
            {
                Chicken_map[i][j] = 987654321;
            }
        }
 
        for (int i = 0; i < Res_count; i++)
        {
            if (Res_visit[i] == 1)
            {
                for (int j = 0; j < House_count; j++)
                {
                    int a = Chicken_map[House[j].y][House[j].x];//기존의 치킨 거리
                    int b = abs(House[j].y, Res[i].y) + abs(House[j].x, Res[i].x);//새로운 치킨집으로 부터의 치킨 거리
                    Chicken_map[House[j].y][House[j].x] = a < b ? a : b;//더 작은 값으로 갱신
                }
            }
        }
 
        int total = 0;
 
        for (int j = 0; j < House_count; j++)
        {
            total += Chicken_map[House[j].y][House[j].x];
        }
        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++;
            }
            else if (map[a][b] == 1)//집 입력
            {
                House[House_count].y = a;
                House[House_count].x = b;
                House_count++;
            }
        }
    }
 
    for (int i = 0; i < Res_count; i++)//M개 추리자~
    {
        Res_visit[i] = 1;
        DFS(i, 1);
        Res_visit[i] = 0;
    }
 
    printf("%d\n", MIN);
 
    return 0;
}