[C++] 삼성 SW 역량 테스트 기출문제 백준 15686 - 치킨 배달

 

 

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

15686번: 치킨 배달

 

 

#include <bits/stdc++.h>
// [C++] 삼성 SW 역량 테스트 기출문제 백준

int ret = INT_MAX;
int n, m;
int map[50][50];


std::vector<std::pair<int, int>> houses;
std::vector<std::pair<int, int>> stores;
std::vector<std::pair<int, int>> sels;


int dist(std::pair<int, int> & lhs, std::pair<int, int> & rhs){
	return std::abs(lhs.first - rhs.first) + std::abs(lhs.second - rhs.second);
}


void dfs(int cnt, int depth) {
	if (cnt == m) {
		int sum = 0;
		for (int i = 0; i < houses.size(); ++i){
			int dis = INT_MAX;
			for (int j = 0; j < sels.size(); ++j){
				dis = std::min(dis, dist(houses[i], sels[j]));
			}
			sum += dis;
		}
		ret = std::min(ret, sum);
		return;
	}

	if (depth == stores.size()) return;

	sels.push_back(stores[depth]);
	dfs(cnt + 1, depth + 1);
	sels.pop_back();
	dfs(cnt, depth + 1);
}


int main()
{
    std::ios_base::sync_with_stdio(false);
    std::cin.tie(nullptr);

	std::cin >> n >> m;
	for (int i = 0; i < n; ++i){
		for (int j = 0; j < n; ++j){
			std::cin >> map[i][j];
			if (map[i][j] == 1){
				houses.push_back({i, j});
			}
			else if (map[i][j] == 2){
				stores.push_back({i, j});
			}
		}
	}

	dfs(0, 0);

	std::cout << ret << '\n';
	return 0;
}