백준 15686 삼성 SW 역량 테스트 기출 문제 c++

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

15686번: 치킨 배달

처음 구상할때 방향성을 어떻게 잡아야할지 생각이 안났다.

입력 수인 N(2 ≤ N ≤ 50)과 M(1 ≤ M ≤ 13) 을 살펴보고 백트래킹을 이용한 브루트포스인걸 알아야했는데 알고리즘 분류표를 보고서야 알았다.

 

생각해보면 2차원 배열 v는 사용할 필요가 없었다. 처음엔 2차원 배열을 이용해 2중 for문으로 경우의수를 하나씩 탐색해 v가 1일때마다 최소값을 찾으려 했는데 그렇게하면 m값을 초과하면서 최소가 나오기 때문에 답이 아니었다.

 

그래서 dfs를 이용한 조합 함수를 사용해 min값을 갱신해주는 식으로 구현했다.

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

int v[51][51];
int n,m;
bool check[14];
int min_sum_tmp = 0;
vector<pair <int,int> > lee;
vector<pair <int,int> > shin;

int min_sum = 9999;


void dfs_combination(int x,int cnt)
{
	if(cnt == m) {
		min_sum_tmp = 0;
		vector<int> check_tmp;
		
		for(int i=0; i<lee.size(); i++) {
			if(check[i]) {
				check_tmp.push_back(i);
			}
		}
		for(int i=0; i<shin.size(); i++) {
			int min_tmp = 9999;
			for(int j=0; j<cnt; j++) {
				int tmp;
				tmp = abs(shin[i].first - lee[check_tmp[j]].first) + abs(shin[i].second - lee[check_tmp[j]].second);
				if(min_tmp > tmp) {
			 		min_tmp = tmp;
				}
			}
			min_sum_tmp = min_sum_tmp + min_tmp;
			
		}
		
		if(min_sum > min_sum_tmp) {
			min_sum = min_sum_tmp;
		}
	}
	
	else {
		for(int i=x; i < lee.size(); i++) {
			if(check[i])	continue;
			check[i] = true;
			dfs_combination(i,cnt+1);
			check[i] = false;
		}
	}
	
}

int main(void)
{
	cin >> n >> m;
	
	for(int i=0; i<n ;i++) {
		for(int j=0; j<n; j++) {
			cin >> v[i][j];
			if(v[i][j] == 2) 
				lee.push_back({i,j});
			else if(v[i][j] == 1) {
				shin.push_back({i,j});
			}
		}
	}
	
	
	
	if(lee.size() < m) {
		m = lee.size();
	}
	
	dfs_combination(0,0);
	
	cout << min_sum;
	
	return 0;
}