백준 15686 치킨 배달

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

#include <iostream>
#include <vector>
#include <cmath>

#define INF 987654321

using namespace std;

vector<pair<int, int>> chk;
vector<pair<int, int>> home;
bool visit[13];
vector<int> chkidx;
int n, m;
int ans=INF;

void dfs(int idx, int cnt){

    if(cnt==m) {
        int s = 0;

        for (int i = 0; i < home.size(); i++) {
            int d = INF;
            for (int j = 0; j < m; j++) {
                int temp = abs(home[i].first - chk[chkidx[j]].first) + abs(home[i].second - chk[chkidx[j]].second);

                d = min(d, temp);
            }
            s += d;
        }

        ans = min(ans, s);

        return;
    }

    for (int i = idx; i < chk.size(); i++) {
        if (!visit[i]) {
            visit[i] = true;
            chkidx.push_back(i);
            dfs(i, cnt + 1);
            chkidx.pop_back();
            visit[i] = false;
        }
    }



}

int main() {

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



    cin >> n >> m;

    vector<vector<int>> arr(n, vector<int>(n));



    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            cin >> arr[i][j];
            if (arr[i][j] == 1) {
                home.push_back(make_pair(i, j));
            }
            else if (arr[i][j] == 2) {
                chk.push_back(make_pair(i, j));
            }
        }
    }

    //chk.size()개의 치킨집 중 m개를 골라야 함
    dfs(0, 0);


    cout << ans;



    return 0;
}

1. 문제

n*n의 지도에 집과 치킨집의 위치가 주어진다. 치킨집 중에서 m개의 치킨집을 뽑아 유지시키고, 나머지는 폐업시키고자한다. 집과 치킨집 사이의 치킨 거리는 abs(집의 x좌표-치킨집의 x좌표)+ abs(집의 y좌표-치킨집의 y좌표)일 때, 치킨집을 어떻게 골라야 도시 전체의 치킨 거리(모든 집의 치킨 거리의 합)가 최소가 되는지, 그 최솟값을 구하는 문제이다.

2. 풀이

 지도에 있는 치킨집 중 m개를 순서에 상관없이 고르는 문제이다. 이는 백트래킹을 사용하여 해결할 수 있다. 치킨집을 사용하는 모든 경우의 수를 고려하여 집과의 치킨거리를 구한 후, 도시거리를 갱신하여 풀 수 있다.

 for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            cin >> arr[i][j];
            if (arr[i][j] == 1) {
                home.push_back(make_pair(i, j));
            }
            else if (arr[i][j] == 2) {
                chk.push_back(make_pair(i, j));
            }
        }
    }

 우선 지도를 입력받으면서 집과 치킨집의 위치를 저장한다.

void dfs(int idx, int cnt){

	...

    for (int i = idx; i < chk.size(); i++) {
        if (!visit[i]) {
            visit[i] = true;
            chkidx.push_back(i);
            dfs(i, cnt + 1);
            chkidx.pop_back();
            visit[i] = false;
        }
    }



}

그 후 인덱스와 선택한 치킨집의 개수를 받는다. 인덱스를 받아야 순열이 아닌 조합을 구할 수 있다. visit 배열로 해당 치킨집이 선택되었는지 확인하고, 선택되지 않았을 경우 해당 인덱스를 추가한다.

void dfs(int idx, int cnt){

    if(cnt==m) {
        int s = 0;

        for (int i = 0; i < home.size(); i++) {
            int d = INF;
            for (int j = 0; j < m; j++) {
                int temp = abs(home[i].first - chk[chkidx[j]].first) + abs(home[i].second - chk[chkidx[j]].second);

                d = min(d, temp);
            }
            s += d;
        }

        ans = min(ans, s);

        return;
    }

 	...



}

 m개의 치킨집을 모두 선택했을 경우 모든 집에서 모든 치킨집에 대한 치킨 거리의 최솟값을 구하고, 이를 도시 거리(s)에 더한다. 계산이 완료되면 ans에 갱신한다. 연산이 끝난 후 ans를 출력하면 정답을 구할 수 있다.