[Algorithm]Baekjoon 15686번 :: 치킨 배달

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

15686번: 치킨 배달

#define MAX_NUM 2147000000
 
struct Pos
{
    int y;
    int x;
};
 
int n, m;
int result = MAX_NUM;
int arr[51][51] = { 0 };
vector<Pos> houses;
vector<Pos> chickenes;
bool visited[14] = { false };
 
 
int calculateDistance(Pos& a, Pos& b)
{
    return abs(a.x - b.x) + abs(a.y - b.y);
}
 
void selectChicken(int index, int count)
{
    
 
    if (count == m) // 치킨집 선택할 수 있는 최대갯수.
    {
        int tempResult = 0;
 
        for (int i = 0; i < houses.size(); i++)
        {
            int distanceToChicken = MAX_NUM;
 
            for (int j = 0; j < chickenes.size(); j++)
            {
                if (visited[j])
                {
                    distanceToChicken = min(distanceToChicken, calculateDistance(houses[i], chickenes[j]));
                }
            }
 
            tempResult += distanceToChicken;
        }
 
        result = min(result, tempResult);
        return;
    }
    if (index == chickenes.size()) return;
    visited[index] = true;
    selectChicken(index + 1, count + 1);
 
    visited[index] = false;
    selectChicken(index + 1, count);
}
 
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
 
    cin >> n >> m;
    
    for (int i = 0; i < n; i++)
    {
        for (int j = 0; j < n; j++)
        {
            cin >> arr[i][j];
            if (arr[i][j] == 1) houses.push_back({ i,j });
            if (arr[i][j] == 2) chickenes.push_back({ i,j });
        }
    }
 
    selectChicken(0,0);
 
    cout << result << endl;
}

2차원배열맵과 최대 선택할 수 있는 치킨집의 개수(M)가 입력으로 주어지고, 도시의 치킨거리를 구하는 문제.

도시의 치킨거리란, 각 집에서 가장 가까운치킨집의 맨하탄거리를 구하고 전부 합쳤을 때의 최소거리이다.

 

'최대로' 선택할 수 있는 치킨집이기 때문에, M개만큼의 치킨집이 선택될 수도 있고, 아닐수도 있다.

이 부분때문에 좀 헷갈려했다..

 

방식자체는 브루트포스이다. M개의 치킨집리스트를 얻었을 때, 각 집을 기준으로 잡고 해당 치킨집리스트를 순회하면서 거리를 계산한다. 최소거리를 구해야하기 때문에 최소값만 구해야 하며, 각 집마다의 치킨집까지의 최소거리값을 구해서 더한 뒤 최종 결과물 result에 갱신한다.

 

최대 허용개수 안에서 각 집을 기준으로 최솟값거리를 계산했기 때문에, 허용개수인데도 너무 혼자 동떨어져있어서 평균값 떨어뜨리는 치킨집까지의 거리는 알아서 반영되지 않는다. 

 

DFS방식이라 방문체크를 스택처럼 관리해도된다.

위 코드는 visited를 어쨌든 전부 돌면서 true인거를 체크해야하기 때문에 조금 개선할 방법이 없나싶어서 구현해봤다.

다만 이번 문제같은 경우는, M이 최대 13밖에 안되서 시간차이는 거의 없긴 했다. M값이 어마어마하게 크다면 조금 차이가 있을 것 같아서, 한번 구현해봤다.

 

#define MAX_NUM 2147000000
 
struct Pos
{
    int y;
    int x;
};
 
int n, m;
int result = MAX_NUM;
int arr[51][51] = { 0 };
vector<Pos> houses;
vector<Pos> chickenes;
vector<int> visited;
 
 
int calculateDistance(Pos& a, Pos& b)
{
    return abs(a.x - b.x) + abs(a.y - b.y);
}
 
void selectChicken(int index)
{
    if (index == chickenes.size()) return;
 
    visited.push_back(index);
    
    if (visited.size() == m) // 치킨집 선택할 수 있는 최대갯수.
    {
        int tempResult = 0;
 
        for (int i = 0; i < houses.size(); i++)
        {
            int distanceToChicken = MAX_NUM;
 
            for (int j = 0; j < visited.size(); j++)
            {
                distanceToChicken = min(distanceToChicken, calculateDistance(houses[i], chickenes[visited[j]]));
            }
 
            tempResult += distanceToChicken;
        }
 
        result = min(result, tempResult);
    }
    else
    {
        selectChicken(index + 1);
    }
    
    visited.pop_back();
    selectChicken(index + 1);
}
 
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
 
    cin >> n >> m;
    
    for (int i = 0; i < n; i++)
    {
        for (int j = 0; j < n; j++)
        {
            cin >> arr[i][j];
            if (arr[i][j] == 1) houses.push_back({ i,j });
            if (arr[i][j] == 2) chickenes.push_back({ i,j });
        }
    }
 
    selectChicken(0);
 
    cout << result << endl;
}