문제

나의 요약

NxN 도시가 있다. 각 칸은 빈칸, 치킨집, 집. 세개중 하나이다. 집과 가장 가까운 치킨집 사이의 거리를 '치킨 거리'라고 하고, 모든 집의 치킨 거리의 합이 '도시의 치킨 거리'이다.
좌표 (r1, c1)과 (r2, c2) 사이의 거리는 |r1-r2| + |c1-c2|로 계산한다.

치킨집 중 최대 M개만 고르고 나머지는 모두 폐업해야 할 때, 어떻게 골라야 '도시의 치킨 거리'가 가장 작게 될까? 가장 최소의 '도시의 치킨 거리'를 출력하자.

접근 방법

백트래킹/DFS 방식으로 전체 치킨집 중 골라야할 M개를 모두 골라서, 그 치킨집들과 집 사이의 거리 중 가장 작은 거리가 그 집의 '치킨 거리'이다. 그것을 모두 더하면 된다.
마치 조합(Combination)의 경우의 수를 뽑아내듯이 경우의 수를 하나씩 뽑아 도시 치킨 거리를 계산하면 된다.
치킨 집의 수는 최대 13이고, 여기서 가장 많은 경우의 수를 가지는 조합은 13C7 = 1716이다. 1716의 경우를 모든 집에 대해 수행하는데, 집은 아무리 많아도 N*N = 250개를 넘을 수 없다. 따라서 최대 반복 수는 대략 1716*250*7(치킨집 수)이다. 이는 1초 안에 실행하기 충분한 반복 수이다.

풀이

#include <bits/stdc++.h>
using namespace std;

int N, M;
vector<pair<int, int>> houses;
vector<pair<int, int>> chickens;
vector<int> combinations;
int ans;

void Input()
{
    cin >> N >> M;
    for(int i = 0; i < N; i++)
    {
        for(int j = 0; j < N; j++)
        {
            int tmp;
            cin >> tmp;
            if(tmp == 1) houses.push_back({i, j});
            else if(tmp == 2) chickens.push_back({i, j});
        }
    }
}

int Distance(int x1, int y1, int x2, int y2)
{
    return abs(x1 - x2) + abs(y1 - y2);
}

void DFS(int idx, int cnt, int end)
{
    if(cnt > 0) combinations[cnt-1] = idx;
    if(cnt == end)
    {
        int sum = 0;
        for(int i = 0; i < houses.size(); i++)
        {
            int minDist = INT_MAX;
            for(int j = 0; j < cnt; j++)
            {
                int chickenIdx = combinations[j];
                int dist = Distance(houses[i].first, houses[i].second, chickens[chickenIdx].first, chickens[chickenIdx].second);
                minDist = min(minDist, dist);
            }
            sum += minDist;
        }
        ans = min(ans, sum);
        return;
    }

    for(int i = idx+1; i < chickens.size(); i++)
    {
        DFS(i, cnt+1, end);
    }
}

void Solve()
{
    ans = INT_MAX;
    combinations.assign(M, 0);
    DFS(-1, 0, M);
    
    cout << ans;
}

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);

    Input();
    Solve();
}

DFS 함수에서 백트래킹을 진행한다. 마치 조합의 경우의 수를 구하듯 combinations 배열에 저장하고, 다음 수를 이어서 진행한다. 만약 M만큼 진행이 되었다면, 지금 combinations 배열에 들어있는 치킨집 인덱스를 통해 모든 집과 선택된 모든 치킨집의 거리를 계산해 도시 치킨 거리를 계산한다. 가장 낮게 나온 치킨 거리를 저장해두었다가 출력하면 된다.

회고

백트래킹 접근 자체는 빠르게 이루어졌다. 하지만 중간에 갑자기 '완전탐색해도 시간이 괜찮나..?' 라는 생각을 해버려 헤매었는데, 대략적으로 시간을 계산해보니 괜찮은 것이 보였다. 그 사이에 시간을 줄이겠다고 이상한 접근을 다시 해버린 것이 문제였지만..
혹시라도 의심이 된다면 주저말고 빠르게 계산해보자!