[c++] 피자배달거리(DFS활용)

피자배달거리

#include <iostream>
#include <vector>
#include <stdlib.h>

/* run this program using the console pauser or add your own getch, system("pause") or input loop */
using namespace std;
int x1, x2, y1, y2, ch[20], sum, dis, min_dis, m, min_res=2147000000;
vector<pair<int, int> > hs;
vector<pair<int, int> > pz;

void DFS(int s, int L) {
		if(L==m) {
			sum=0;
			for(int i=0; i<hs.size(); i++){
				x1=hs[i].first;
				y1=hs[i].second;
				min_dis=2147000000;
				for(int j=0; j<m; j++){
					x2=pz[ch[j]].first;
					y2=pz[ch[j]].second;
					dis = abs(x1-x2)+abs(y1-y2);
					if(min_dis>dis) min_dis=dis;
				}
				sum+=min_dis;
			}
			if(min_res>sum) min_res=sum;
		}
	    else {
	    	for(int i=s; i<pz.size(); i++){
				ch[L]=i;
				DFS(i+1, L+1);
			}
		}
}
int main() {
	int n, k;
	//freopen("input.txt", "rt", stdin);
	cin>>n>>m;
	for(int i=1; i<=n; i++){
		for(int j=1; j<=n; j++){
			cin>>k;
			if(k==1) hs.push_back(make_pair(i, j)); 
			else if(k==2) pz.push_back(make_pair(i, j));
		}
	}
	DFS(0, 0);
	printf("%d\n", min_res);
	return 0;
}

처음 문제를 접근 할 때 그냥 이중배열에 넣고 그 배열중에서 1과 2를 가려서 계산을 하려고 했었다.

그렇게 하다 잘 풀리지 않아서 강의 코드를 약간 참고했는데

피자집과 집을 각각 pz, hs로 배열을 만들어서 make_pair를 통해 좌표로 각각 넣었다. 

그 후 DFS 조합과정을 통해 ch배열에 선택된 피자집의 인덱스를 넣고 

선택된 피자집과 집들사이의 거리를 구해준다.

 

여기에서 내가 헷갈렸던 것이 있는데

최소값이라해서 어느 한 집과 피자집1, 피자집2, ... 선택된 피자집들간의 거리를 각각 구하고 이 거리중

가장 짧은 거리를 sum에 더해주어야 하는데 그 거리를 모두 더해서 생각보다 큰값이 나왔었다.

어느 한 집이 있으면 어느 피자집에 배달을 시키는 것이 가장 거리가 짧은지 먼저 비교하고

이 과정을 통해 가장 짧은 거리가 나오면 그 거리를 sum에 더해준다.