[백준 15686번] 치킨 배달

문제 링크: https://www.acmicpc.net/problem/15686

15686번: 치킨 배달

<문제 풀이> 시뮬레이션 + 조합

문제에서 최대 M개의 치킨집을 선택할 수 있다고 했는데 치킨집의 개수가 많을수록 치킨 거리가 더 짧아지니깐 그냥 M개의 치킨집을 뽑는 조합을 구현하면 된다.

 

 

<C++ 소스 코드>

#include <iostream>
#include <string>
#include <algorithm>
#include <queue>
#include <vector>
#include <stack>
#include <utility>
#include <climits>
#include <cmath>
#include <deque>
#include <cstdlib>
using namespace std;
 
int board[50][50];
bool choose[50][50];
int N, M;
int res = 2500;
vector<pair<int, int> > chicken;
vector<pair<int, int> > house;
 
void dfs(int idx, int depth) {
    if (depth == M) {
        int sum = 0;
        for (auto h : house) {
            int r1 = h.first;
            int c1 = h.second;
            int chicken_dist = 2500;
            for (auto c : chicken) {
                int r2 = c.first;
                int c2 = c.second;
                if (choose[r2][c2]) {
                    int dist = abs(r1 - r2) + abs(c1 - c2);
                    chicken_dist = min(chicken_dist, dist);
                }
            }
            sum += chicken_dist;
 
        }
        res = min(res, sum);
        return;
    }
    int chicken_size = chicken.size();
    for (int i = idx; i < chicken_size; i++) {
        int r = chicken[i].first;
        int c = chicken[i].second;
        choose[r][c] = true;
        dfs(i + 1, depth + 1);
        choose[r][c] = false;
    }
}
 
 
 
int main(void) {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    
    cin >> N >> M;
 
    for (int i = 0; i < N; i++) {
        for (int j = 0; j < N; j++) {
            cin >> board[i][j];
            if (board[i][j] == 2) chicken.push_back({ i, j });
            if (board[i][j] == 1)house.push_back({ i, j });
        }
    }
    dfs(0, 0);
 
    cout << res;
  
 
    return 0;
}