[백준/BOJ] 15686번 치킨 배달 (C++)

www.acmicpc.net/problem/15686

15686번: 치킨 배달

삼성 역량 테스트 기출 문제 : DFS(조합) + 시뮬레이션(구현)

DFS를 이용하여 조합을 잘 얻어낼 수 있다면 구현도 까다롭지 않아서 어렵지 않게 해결할 수 있는 문제입니다. (next_permutation으로도 조합을 구할 수 있습니다.)

 

1. 전체 치킨가게의 수에서 m개를 정하는 조합을 구한다.

2. 해당 조합에서 치킨집과 집의 치킨 거리(최소 거리)를 구한다.

3. 이를 더한 값이 최소가 되는 것을 찾아서 마지막에 출력한다.

 

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

const int MMAX = 52;
const int CMAX = 15;
const int VMAX = 2147000000;

int map[MMAX][MMAX];
int tmp[CMAX];
vector<pair<int, int > > house, chicken;
int n, m, answer = VMAX; 

// 해당 조합에서 집에서 치킨집까지의 최소 거리를 각각 구하고 합함  
int getChickenDistance() {
	int disSum = 0;
	for(int i = 0; i < house.size(); i++) {
		int disEach = VMAX;
		int hx = house[i].first;
		int hy = house[i].second;
		for(int j = 0; j < m; j++) {
			int cx = chicken[tmp[j]].first;
			int cy = chicken[tmp[j]].second;
			disEach = min(disEach, abs(hx - cx) + abs(hy - cy));
		}
		disSum += disEach;
	}
	return disSum;
}

// DFS : 총 치킨집에서 m개를 구하는 조합  
void DFS(int idx, int cnt) {
	if(cnt == m) {
		// 최소거리들의 합 중에서 가장 작은 것을 구해야 함 
		answer = min(answer, getChickenDistance());
		return;
	} else {
		for(int i = idx; i < chicken.size(); i++) {
			tmp[cnt] = i;
			DFS(i + 1, cnt + 1);
		}
	}
}

int main(void) {
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    
    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] == 2) chicken.push_back({i, j});
    		else if(map[i][j] == 1) house.push_back({i, j});
		}
	}
	
	DFS(0, 0);
	cout<<answer;
}

 

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

const int MMAX = 52;
const int VMAX = 2147000000;

int map[MMAX][MMAX];
vector<pair<int, int > > house, chicken;
int n, m, answer = VMAX; 

int main(void) {
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    
    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] == 2) chicken.push_back({i, j});
    		else if(map[i][j] == 1) house.push_back({i, j});
		}
	}
	
	// 앞에 m개는 0, 나머지는 1로 벡터를 초기화 (0 부분이 치킨 집) 
	vector<int> check(chicken.size(), 1);
	for(int i = 0; i < m; i++) {
		check[i] = 0;
	}
	
	// next_permutation을 이용한 조합 구하기  
	do {
		int disSum = 0;
		for(int i = 0; i < house.size(); i++) {
			int disEach = VMAX;
			int hx = house[i].first;
			int hy = house[i].second;
			for(int j = 0; j < chicken.size(); j++) {
				if(check[j] == 1) continue;
				int cx = chicken[j].first;
				int cy = chicken[j].second;
				disEach = min(disEach, abs(hx - cx) + abs(hy - cy));
			}
			disSum += disEach;
		}
		answer = min(answer, disSum);
	} while(next_permutation(check.begin(), check.end()));
	
	cout<<answer;
}