치킨 배달 (feat. 백준, 15686번)

치킨 배달
https://www.acmicpc.net/problem/15686

15686번: 치킨 배달

 

반응형

 

// woohyeon.kim
// kim519620.tistory.com
#include <iostream>
#include <string.h>
#include <vector>
#include <algorithm>
using namespace std;
int N, M, arr[51][51], ans;
bool visit[13];
vector<pair<int, int>> all_chicken_stores;
pair<int, int> chicken_stores[13];
int get_chicken_range(register int x, register int y){
    register int range = 99999999;
    for(register int m = 0; m < M; ++m)
        range = min(range, abs(chicken_stores[m].first - x) + abs(chicken_stores[m].second - y));
    return range;
}
void dfs(register int idx, register int cnt){
    if(cnt == M){
        register int chicken_range = 0;
        for(register int i = 1, j; i <= N; ++i)
            for(j = 1; j <= N; ++j)
                if(arr[i][j] == 1)
                    chicken_range += get_chicken_range(i, j);
        ans = min(ans, chicken_range);
        return;
    }
    for(register int i = idx; i < all_chicken_stores.size(); ++i)
        if(!visit[i]){
            visit[i] = true;
            chicken_stores[cnt] = all_chicken_stores[i];
            dfs(i + 1, cnt + 1);
            visit[i] = false;
        }
}
int main(){
    ios::sync_with_stdio(false), cin.tie(NULL);
    memset(visit, false, sizeof(visit));
    cin >> N >> M;
    for(register int i = 1, j; i <= N; ++i)
        for(j = 1; j <= N; ++j){
            cin >> arr[i][j];
            if(arr[i][j] == 2)
                all_chicken_stores.push_back(make_pair(i, j));
        }
    ans = 99999999;
    dfs(0, 0);
    cout << ans;
    return 0;
}
// *&)*@*

 

 

1. 제가 좋아하는 시뮬레이션 + 그래프 탐색 문제입니다.
2. N개 중 M개의 치킨집 조합을 구합니다.
3. 각각의 조합을 구한 경우, 각 도시와 모든 치킨집에 대해 가장 가까운 거리를 구합니다.
4. 모든 도시에 대해서 3번을 구하고 그 합을 구합니다. 해당 합은 하나의 조합에 대한 SUM 값입니다.
5. 따라서 모든 조합에 대한 각각의 SUM 중 최소값을 찾아주면 되겠습니다.