[시뮬레이션] BOJ 15686 - 치킨 배달 with c++

 

15686번: 치킨 배달 (acmicpc.net)

15686번: 치킨 배달

 

접근 방법

1. 폐업하지 않을 치킨집 M개를 선택한다.

2. 해당 폐업하지 않은 치킨집들과 집 사이의 거리들의 합 중 최소값을 구한다.

 

위 두 가지가 이번 문제의 핵심이다.

 

폐업하지 않을 치킨집을 고르는 방법 브루트포스밖에 없는 거 같다.

시간을 줄이기위해 백트래킹을 이용하기로 했다.

 

선택된 M개의 치킨집들과 집과의 거리의 최솟값을 구하기 위해

각 집마다 치킨집들과의 거리를 재어보고 이 중 가장 작은 것을 최종값에 더했다.

 

복잡한 문제는 아니므로 한번 풀어보자.

 

코드

#include<iostream>
#include<algorithm>
#include<queue>
#include<vector>
#include<cmath>
#include<cstring>

#define MAX 51
#define INF 9999999

using namespace std;

int n, m;
int res = INF;
int arr[MAX][MAX];
vector<pair<int, int>> chicken;
vector<pair<int, int>> home;
vector<int> selected;

int count() {
	int total = 0;
	for (int i = 0; i < home.size(); i++) {
		int tmp = INF;
		for (int j = 0; j < m; j++) {
			tmp = min(
				abs(home[i].first - chicken[selected[j]].first) +
				abs(home[i].second - chicken[selected[j]].second)
				, tmp
			);
		}
		total += tmp;
	}
	//cout << "total: " << total << endl;
	return total;
}

void select(int cnt, int idx) {
	if (cnt == m) {
		int tmp = count();
		//cout << "tmp: " << tmp << endl;
		res = min(res, tmp);
		return;
	}

	for (int i = idx; i < chicken.size(); i++) {
		selected.push_back(i);
		//cout << "selected: " << i << endl;
		select(cnt + 1, i + 1);
		selected.pop_back();
	}
}

int main() {
	cin.tie(NULL); ios_base::sync_with_stdio(false);
	cin >> n >> 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)
				chicken.push_back(make_pair(i, j));
		}
	}
	select(0, 0);
	cout << res;
}