[BOJ] 치킨 배달 15686 (C++) - 44

문제

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

15686번: 치킨 배달

생각

브루트포스 알고리즘으로 전체를 다 순회해야 한다.

모든 집에 대한 모든 치킨집까지의 거리를 계산해 최솟값을 저장한다.

 

치킨집을 고르는 과정에서는 조합을 이용해 치킨집을 고르면 된다.

void dfs(int idx, int chosen) {
    if(chosen == m) {
        int tmpSum = 0;
        for(int i = 0; i < h.size(); i++) {
            int minDst = MAXN;
            for(int j = 0; j < c.size(); j++) {
                if(vst[j])
                    minDst = min(minDst, distance(h[i], c[j]));
            }
            tmpSum += minDst;
        }
        result = min(result, tmpSum);
        return;
    }
    if(idx == c.size()) return;
    //프랜차이즈 선정
    vst[idx] = true;
    dfs(idx + 1, chosen + 1);
    //프랜차이즈 선정 X
    vst[idx] = false;
    dfs(idx + 1, chosen);
}

vst[] 라는 bool 1차원 배열을 만들어 true, false를 통해 치킨집의 조합을 구하자.

 

코드

#include <iostream>
#include <vector>
using namespace std;

typedef pair<int, int> pii;
const int MAXN = 987654321;

int map[50][50];
int n, m;
vector<pii> h;
vector<pii> c;
int result = MAXN;
bool vst[14] = {false};

int distance(pii a, pii b){
   return abs(a.first - b.first) + abs(a.second - b.second);
}

void dfs(int idx, int chosen) {
    if(chosen == m) {
        int tmpSum = 0;
        for(int i = 0; i < h.size(); i++) {
            int minDst = MAXN;
            for(int j = 0; j < c.size(); j++) {
                if(vst[j])
                    minDst = min(minDst, distance(h[i], c[j]));
            }
            tmpSum += minDst;
        }
        result = min(result, tmpSum);
        return;
    }
    if(idx == c.size()) return;
    //프랜차이즈 선정
    vst[idx] = true;
    dfs(idx + 1, chosen + 1);
    //프랜차이즈 선정 X
    vst[idx] = false;
    dfs(idx + 1, chosen);
}

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

    cin >> n >> m;

    for(int i = 0; i < n; i++) {
        for(int j = 0; j < n; j++) {
            cin >> map[i][j];
            if(map[i][j] == 1) h.push_back({i, j});
            else if(map[i][j] == 2) c.push_back({i, j});
        }
    }

    dfs(0, 0);
    cout << result;
}