백준 15686 - 치킨 배달 (c++ 풀이)

1. 문제

---

2. 유랑자의 풀이 전략 - BFS는 시간초과 -> 단순 최소합 구하기 / 조합

 

• bfs로 풀었다가 시간초과가 났다. 간과한 점은, 경로 중에 다른 집이 있어도 상관없다는 것이다. 이 점 때문에 bfs로 구현할 필요가 없어졌다. 단순히 한 집에 대해 선택한 치킨집들에 대해 멘헤튼 거리의 최소값을 구해주면 되었다. 

1) 최대 m개의 치킨 집을 선택하는 조합함수 comb를 활용해 치킨집을 선택한다.

2) 선택된 치킨집에 대해 최소 맨해튼 거리를 구하는 minValue 함수를 통해 결론을 도출한다.

---

3. 풀이 비교

• 다음은 얍문님의 풀이와 비교한 후기입니다.(링크 : https://yabmoons.tistory.com/50)

풀이 알고리즘은 같습니다. 이러한 문제는 거의 대부분 비슷한 풀이일 겁니다. 따라서 자료구조, 메모리 측면에서 한번 분석해 보았습니다. 이쪽에 대한 이론적 공부를 하지 못해 뇌피셜적으로 해석했습니다. 잘못된 점이나 조언할 부분 있다면 댓글로 부탁드리겠습니다.

 

우선 얍문님은, 치킨집을 선택하여  벡터 v에 실시간으로 저장했습니다. 때문에 선택된 치킨집들에 대한 연산만 수행하면 됩니다.

유랑자는, bool 배열 select에 치킨집 선택여부를 저장했습니다. 이에 모든 치킨집에 대해 순회하면서 select가 된 치킨집에 한해서 연산을 수행해야 했습니다. 결국 더 많은 연산을 수행하게 되어 효율적이지 못하게 될 것입니다.

 

무슨 차이일까요?

얍문님의 직접 저장을 통해 한번의 확인이 필요하지만, 유랑자는 순회하면서 1번, 그것이 선택된 치킨집인가에 대해서 2번으로 총 2번의 확인이 필요하게 된 것입니다.

 

=> 결론 : 얍문님처럼 직접 저장 방식을 활용해보자.

 

 

• 다음은 구데타마님의 풀이와 비교한 후기입니다.(링크 : https://jaimemin.tistory.com/1059)

알고리즘은 같은데 구현방식이 조금 다릅니다? 맞는 문장인지... 

구데타마님은 치킨집을 선정하는 조합을 구현하는 dfs에서 선택 or 버림 두 가지의 경우로 재귀를 돌립니다. 가끔 봐왔긴 했지만 다른 방식이고 최대한 여러 구현방식을 알아보자는 유랑자의 취지에 부합해 포스트하게 되었습니다.

유랑자는 전통적인 콤비네이션 경우의 수를 따져가며 dfs를  돌립니다.

각 경우 수를 따져보면 유랑자식의 dfs가 조금 덜 따지긴 합니다만 큰 차이는 아닌 것 같습니다.

 

=> 결론 : 이분법적 dfs 방식도 있으니 참고하자.

---

3. 코드

#include <iostream>
#include <string>
#include <algorithm>
#include <vector>
#include <string.h> // memset 
#include <math.h>
#include <queue>
#define INF 987654321
using namespace std;

int n, m, map[51][51], ans=INF, homes_size, stores_size;
vector<vector<int> > homes, stores;
bool visit[51][51], selected[51][51];
int dx[4]={1, 0, -1, 0}, dy[4]={0, 1, 0, -1};

void init(){
	cin >> n >> m;
	for(int i=1; i<=n; i++){
		for(int j=1; j<=n; j++){
			cin >> map[i][j];
			if(map[i][j]==1) homes.push_back({i, j});
			else if(map[i][j]==2) stores.push_back({i, j});
		}
	}

	homes_size=homes.size();
	stores_size=stores.size();
	return ;
}

int minValue(int x, int y){
	int ret=INF;
	for(int i=0; i<stores_size; i++){
		int tx=stores[i][0], ty=stores[i][1];
		if(!selected[tx][ty]) continue;
		
		int dist=abs(tx-x)+abs(ty-y);
		if(ret>dist) ret=dist; 
	}
	
	return ret;
}

void comb(int depth, int start){
	if(depth==m){
		int sum=0;
		for(int i=0; i<homes_size; i++){
//			int ret=bfs(homes[i][0], homes[i][1], sum);
//			if(ret==-1) return ;
			sum+=minValue(homes[i][0], homes[i][1]);
			memset(visit, 0, sizeof(visit));
		}
		if(sum<ans) ans=sum;
			
		return ;
	}
	
	for(int i=start; i<stores_size-m+depth+1; i++) {
		int x=stores[i][0], y=stores[i][1];

		selected[x][y]=true;
		comb(depth+1, i+1);
		selected[x][y]=false;
	}
	
	return ;
}

int main(){
	ios::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);

	init();

	vector<vector<int> > a;
	comb(0, 0);
	
	cout << ans;
	return 0;
}

// 아래는 bfs 시간초과 났던 코드 일부분입니다. 

//int bfs(int x, int y, int &sum){
//	queue<vector<int> > q;
//	q.push({x, y});
//	visit[x][y]=true;
//	
//	while(!q.empty()){
//		int q_size=q.size();
//		bool flag=false;
//		while(q_size--){
//			int tx=q.front()[0], ty=q.front()[1];
//			q.pop();
//			
//			for(int i=0; i<4; i++){
//				int nx=tx+dx[i], ny=ty+dy[i];
//				if(nx<1 || n<nx || ny<1 || n<ny || visit[nx][ny]) continue;
//				if(map[nx][ny]==2 && selected[nx][ny]){
//					flag=true;
//					break;
//				}
//				
//				q.push({nx, ny});
//				visit[nx][ny]=true;
//			}		
//		}
//		sum++;
//		if(ans<sum) return -1;
//		if(flag) break;		
//	}
//	
//	return 1;	
//}