피자 배달 거리 문제 - DFS 활용 , 순열 조합 활용

첫 코드

#include <bits/stdc++.h>
using namespace std;

int n,m, arr[51][51], ch[20], minn=INT_MAX;
vector<pair<int,int> > v;

void DFS(int node){
	if(node==m){
		int cnt=0;
		//도시 피자배달 거리 구하기  
		//ch[i]==1 이면 선택된 피잣집 
		
		for(int i=1; i<=n; i++){
			for(int j=1; j<=n; j++){
				int min_dist=INT_MAX;
				if(arr[i][j]==1){
					for(int k=0; k<v.size(); k++){
						if(ch[k]==1){
							int cur_dist = abs(i-v[k].first)+abs(j-v[k].second);
							if(min_dist>cur_dist){
								min_dist = cur_dist;
							}
							
						}
						else continue;
					}
					cnt += min_dist;
				}
			}
			
		} 
		if(cnt<minn) minn=cnt;
		
	}
	else{
		for(int i=0; i<v.size(); i++){
			if(ch[i]==0){
				ch[i]=1;
				DFS(node+1);
				ch[i]=0;
			}
		}	
		
	}
	
}

int main(){
	//freopen("input.txt.txt","rt",stdin);
	ios::sync_with_stdio(false);
	cin.tie(0);

	// 피잣집 선택 갯수 
	// 6개중 4개 선택 ---> 거리 최솟값 
	
	int i,j;
	// 피잣집 벡터 
	
	
	scanf("%d %d",&n, &m);
	
	
	for(i=1; i<=n; i++){
		for(j=1; j<=n; j++){
			scanf("%d",&arr[i][j]);
			
			if(arr[i][j]==2) {
				v.push_back(make_pair(i, j));
			}
		}
	}
	// 피잣집 선택  
	DFS(0);
	
	printf("%d",minn);
	
}

문제점

 

1. 피잣집을 구할 때 순열로 뽑았다. DFS에서 경우의수가 불필요하게 많이 계산된다.

 

2. 필요한 정보는 집과 피자집의 좌표인데 그 외의 불필요한 좌표를 모두 돌면서 시간이 오래걸린다.

 

 

1차 수정

#include <bits/stdc++.h>
using namespace std;

int n, m, ch[20], minn=INT_MAX;
vector<pair<int, int> > hs;
vector<pair<int, int> > pz;

void DFS(int s, int L){
	if(L==m){
		int cnt = 0;
		for(int i=0; i<hs.size(); i++){
			int hs_min =INT_MAX;
			for(int j=0; j<pz.size(); j++){
				if(ch[j]==0) continue;
				int hs_dist = abs(hs[i].first-pz[j].first) + abs(hs[i].second - pz[j].second);
				if(hs_min> hs_dist) hs_min = hs_dist;
			}
			cnt += hs_min;	
		}
		if(minn>cnt) 
		{
			minn=cnt;

		}
	}
	else{
		//피자집 순열 구함  
		for(int i=s; i<pz.size(); i++){
			ch[i] = 1;
			DFS(i+1, L+1);
			ch[i] = 0;
		}
	}
}


int main(){
	//freopen("input.txt.txt","rt",stdin);
	ios::sync_with_stdio(false);
	cin.tie(0);
	int i, j,tmp;
	
	scanf("%d %d",&n,&m);
	
	for(i=0; i<n; i++){
		for(j=0; j<n; j++){
			scanf("%d", &tmp);
			if(tmp==1){
				hs.push_back(make_pair(i,j));
			}
			else if(tmp==2){
				pz.push_back(make_pair(i,j));
			}
		}	
	}
	
	DFS(0,0);
	printf("%d",minn);
	
	
}

ch배열에 해당하는 피잣집 인덱스를 직접 넣는게 아니라

피잣집 인덱스가 해당하면 표시해주는 방법으로 했다.

 

ch[0] = 1 이면 0번 피잣집이 조합에 포함되고, ch[1] = 0 이면 1번 피잣집은 조합에 포함되지 않는 걸로 지정했다.

이렇게하면 반드시 체크를 해제해주는 과정이 필요하다.

 

ch배열에 해당 피잣집 인덱스를 직접 넣어주면 더 간단하게 풀 수 있다.

예를들어 ch[0] = 1 ch[1] = 2 ch[2] = 3 이렇게하면 1번, 2번, 3번 피잣집이 해당한다.

 

 

#include <bits/stdc++.h>
using namespace std;

int n, m, ch[20], minn=INT_MAX;
vector<pair<int, int> > hs;
vector<pair<int, int> > pz;

void DFS(int s, int L){
	if(L==m){
		int cnt = 0;
		for(int i=0; i<hs.size();i++){
			int hs_min = INT_MAX;
			for(int j=0; j<m; j++){
				int dist =abs(pz[ch[j]].first - hs[i].first) + abs(pz[ch[j]].second - hs[i].second);
				if(hs_min > dist) hs_min = dist;
			}
			cnt+=hs_min;
		}
		if(minn>cnt) minn = cnt;
	}
	else{
		//피자집 순열 조합  구함  
		for(int i=s; i<pz.size(); i++){
			ch[L] = i;
			DFS(i+1, L+1);
		}
	}
}


int main(){
	//freopen("input.txt.txt","rt",stdin);
	ios::sync_with_stdio(false);
	cin.tie(0);
	int i, j,tmp;
	
	scanf("%d %d",&n,&m);
	
	for(i=0; i<n; i++){
		for(j=0; j<n; j++){
			scanf("%d", &tmp);
			if(tmp==1){
				hs.push_back(make_pair(i,j));
			}
			else if(tmp==2){
				pz.push_back(make_pair(i,j));
			}
		}	
	}
	
	DFS(0,0);
	printf("%d",minn);
	
	
}

ch 배열에 직접 해당 피잣집의 인덱스를 넣어주니 코드가 더 간결해졌다.

 

 

 

순열 조합 문제

https://dingcoding.tistory.com/entry/%EB%B0%B1%EC%A4%80-15650%EB%B2%88-N%EA%B3%BC-M-2-%EC%88%9C%EC%97%B4%EC%9D%98-%EC%A1%B0%ED%95%A9-%EB%AC%B8%EC%A0%9C-DFS%EB%A1%9C-%ED%92%80%EA%B8%B0