백준 15686 치킨 배달 c++

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

15686번: 치킨 배달

역대급으로 오래 걸린 문제였다. 시간초과로 방법을 계속 바꿨다.

1. board로 받아서 매번 bfs돌았다. ->  store pair만듬 ->house도 pair배열 만들어서 해결

2. 조합 만들어서 치킨거리 구해줌 -> 이미 너무 안골라서 남은 경우 다 골라도 wantcnt 못 채우는 경우 미리 종료

2번의 경우 생각하다가 탈모오는줄 알았다. 가게 없애는 경우, 안없애는경우 둘다 if 설정해 줬다가 엄청 헤맸다.

if (storeV.size() == depth)

return ;

이게 핵심이다. 글러먹은 경우 먼저 가지치기 해줌.

 

망했을땐 걍 밀고 새로 하자. 그게 더 빠르다

거의 4시간 걸려 푼 문젠데 너무 시간 아깝다 다음 문제부턴 시간 재고 1시간 지나도 안되면 걍 풀이 보자;

#include <iostream> // 통과하지만 32ms 걸리는 똥풀이
#include <string>
#include <vector>
#include <algorithm>
#include <deque>
#include <unordered_set>
#include <cstring>
#include <utility>
#include <climits> // int32max

using namespace	std;

int len, res = 2147483647, store = 0, closeCnt = 0;
vector<vector<int> > board;
vector<pair< int, int> > storeV;

int	getChickenDist() {
	int sum = 0;
	for (int i = 0; i < len; i++) {
		for (int j = 0; j < len; j++) {
			int dist = 2147483647;
			if (board[i][j] == 1) {
				for (int k = 0; k < storeV.size(); k++) {
					if (storeV[k].first == -1) // 이미 없앤 매장이면
						continue;
					int curDist = abs(storeV[k].first - i) + abs(storeV[k].second - j);
					dist = min(dist, curDist);
				}
				sum += dist;
			}
		}
	}
	return sum;
}


void	dfs(int depth) {
	if (closeCnt == 0) { // 다 줄였으면
		res = min(getChickenDist(), res);
		return ;
	}
	if (storeV.size() == depth)
		return ;
	vector<vector<int> > backup(board);
	vector<pair< int, int> > backup2(storeV);
	board[storeV[depth].first][storeV[depth].second] = 0;
	storeV[depth].first = -1;
	closeCnt--;
	dfs(depth + 1);
	closeCnt++;
	board = backup;
	storeV = backup2;
	dfs(depth + 1);
}


int	main()
{
	ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);

	cin >> len >> store;
	vector<vector<int> > v(len, vector<int>(len));
	board = v;
	for (int i = 0; i < len; i++) {
		for (int j = 0; j < len; j++) {
			cin >> board[i][j];
			if (board[i][j] == 2) {
				storeV.push_back(make_pair(i, j));
				closeCnt++;
			}
		}
	}
	closeCnt -= store;
	dfs(0);
	cout << res;
}

아래는 다른 사람들의 코드를 참조한 좋은 풀이 무려 4ms ㄷ ㄷ

#include <iostream> // 더 좋은 풀이
#include <string>
#include <vector>
#include <algorithm>
#include <deque>
#include <unordered_set>
#include <cstring>
#include <utility>

using namespace	std;

int len, res = 2147483647, wantCnt;
vector<pair<int, int> > store;
vector<pair<int, int> > house;
int selectArr[15];
int selectIdx = 0;

int getChickenDist() {
	int sum = 0;
	for (int i = 0; i < house.size(); i++) {
		int diff = 2147483647;
		for (int j = 0; j < wantCnt; j++) {
			int cur = abs(store[selectArr[j]].first - house[i].first)
				 + abs(store[selectArr[j]].second - house[i].second);
			diff = min(diff, cur);
		}
		sum += diff;
	}
	return sum;
}

void dfs(int depth) {
	if (selectIdx == wantCnt) {
		res = min(getChickenDist(), res);
		return ;
	}
	if (depth == store.size())
		return; // 더 이상 탐색할 필요 없음
	selectArr[selectIdx++] = depth;
	dfs(depth + 1);
	selectIdx--;
	dfs(depth + 1);
}

int	main()
{
	ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
	int input;
	cin >> len >> wantCnt;
	for (int i = 0; i < len; i++) {
		for (int j = 0; j < len; j++) {
			cin >> input;
			if (input == 2)
				store.push_back(make_pair(i, j));
			if (input == 1)
				house.push_back(make_pair(i, j));
		}
	}
	dfs(0);
	cout << res;
}