[백준][C++] 15686: 치킨 배달

문제 링크: https://www.acmicpc.net/problem/15686

 

완전 탐색 문제입니다. 모든 경우의 수 만들어서 치킨 거리의 최솟값 구하면 되는 간단한 문제입니다.

별로 어렵지는 않은데 시간 초과가 나지 않도록 유념해야 하는 부분이 있습니다.

 

먼저 vector를 사용할 때는 size 함수 호출 횟수를 최소화 해야됩니다.

vector<int> v;
v.resize(10);
for (int i=0; i<v.size(); ++i)
	v[i] = i;
    
//////////////////////////////////////

vector<int> v;
v.resize(10);
const int& sz = v.size();
for (int i=0; i<sz; ++i)
	v[i] = i;

보통 for문 condition에 size() 함수를 쓸텐데, 매 루프마다 호출되기 때문에 size가 고정된 값이라면 상수로 따로 빼주는게 실행속도를 빠르게 할 수 있을 겁니다.

 

그리고 더 중요한 점이, 같은 답을 중복으로 세는 경우를 없애야 합니다.

예를 들어 이 문제에서는 M개의 치킨집을 만들 때 0개부터 하나씩 추가하거나, 아니면 현재 치킨집에서 하나씩 없애가는 식으로 푸실 겁니다. 방법의 차이는 있지만 완전탐색인 점은 동일합니다.

치킨집을 하나씩 추가해가면서 M개의 치킨집이 되면 그때 치킨 거리를 계산한다고 생각해봅시다.

int n, m;
const int INF = 987654321;
vector<pair<int, int>> houses;
vector<pair<int, int>> chicken_stores;

int visited[50][50];

//...

int get_max_chicken_dist(vector<pair<int,int>>& remain_stores) {
	const int& sz = remain_stores.size();

	if (sz < m) {
		int ret = INF;
		
		for (auto& c : chicken_stores) {
			if (!visited[c.first][c.second]) {
				remain_stores.push_back(c);
				visited[c.first][c.second] = 1;
				
				ret = min(ret, get_max_chicken_dist(remain_stores));
				
				remain_stores.pop_back();
				visited[c.first][c.second] = 0;
			}
		}

		return ret;
	}

	//...
}

 

위 코드는 얼핏 보면 문제가 없어 보입니다. 그런데 사실 \(sz<m\) 부분이 잘못됐습니다.

sz는 지금까지 치킨집을 몇 개 골랐는지 정보밖에 없기 때문에, 안쪽의 루프에서 다시 앞쪽 치킨집을 고르는 경우가 생기고, 이 때문에 시간복잡도가 올라가게 됩니다.

 

중복으로 세는 경우를 방지하기 위한 좋은 방법은 항상 특정 형태를 갖는 갖는 답만을 세는 것입니다. 흔히 사용하는 방법으로는 사전순으로 가장 먼저 오는 답 하나만 세는 것이 있습니다.

 

위 코드에서는 지금까지 몇 개의 치킨집을 골랐는지 인덱스를 함수에 같이 넘기면 사전순으로 답을 선택해 중복으로 세는 경우를 없앨 수 있습니다.

 

 

책에서 배운 부분인데 아직 몸에 배지가 않았네요 ㅠㅠ 시간초과때문에 몇 번 틀렸습니다.

 

#define _CRT_SECURE_NO_WARNINGS
#include <bits/stdc++.h>

using namespace std;

int n, m;
const int INF = 987654321;
vector<pair<int, int>> houses;
vector<pair<int, int>> chicken_stores;

int visited[50][50];


int manhattan_dist(const pair<int, int>& p1, const pair<int, int>& p2) {
	return abs(p1.first - p2.first) + abs(p1.second - p2.second);
}

int get_max_chicken_dist(vector<pair<int,int>>& remain_stores, int curr) {
	const int& sz = remain_stores.size();
	const int& chicken_sz = chicken_stores.size();

	if (sz < m) {
		int ret = INF;
		
		for (int i = curr+1; i < chicken_sz; ++i) {
			auto c = chicken_stores[i];

			if (!visited[c.first][c.second]) {
				remain_stores.push_back(c);
				visited[c.first][c.second] = 1;
				
				ret = min(ret, get_max_chicken_dist(remain_stores, i));
				
				remain_stores.pop_back();
				visited[c.first][c.second] = 0;
			}
		}

		return ret;
	}

	int ret = 0;
	for (auto& h : houses) {
		int min_dist = INF;
		for (auto& s : remain_stores) {
			min_dist = min(min_dist, manhattan_dist(h, s));
		}
		ret += min_dist;
	}

	return ret;
}


int main(int argc, char** argv)
{
#ifndef ONLINE_JUDGE
	freopen("input.txt", "r", stdin);
#endif

	ios_base::sync_with_stdio(false);
	cin.tie(NULL);

	int tmp;
	cin >> n >> m;
	houses.reserve(2 * n);
	chicken_stores.reserve(13);

	for (int i = 0; i < n; ++i) {
		for (int j = 0; j < n; ++j) {
			cin >> tmp;
			switch (tmp) {
			case 1:
				houses.push_back(make_pair(i, j));
				break;

			case 2:
				chicken_stores.push_back(make_pair(i, j));
				break;
			}
		}
	}
	memset(visited, 0, sizeof(visited));
	vector<pair<int, int>> v;
	v.reserve(13);
	cout << get_max_chicken_dist(v, -1);
	
	return 0;
}

대충 짰습니다. 참고만 해주세요.