치킨 배달 15686

1. 기본 설명

전형적인 브루트포스로 풀 수 있다. 이게 현재 solve.ac기준 골드 5라 책정되어있는데
아마 순열 조합 뽑기가 섞여있어 그런거 아닌가 싶다.

내가 푼 방법은 브루트포스라는 이름에 가장 걸맞는 방법으로, 현존하는 치킨집을 M개 맞춰 combination으로 다 뽑은 다음, 모든 가능한 경우에 대해 min값을 찾는다.

코드를 한번 봐 보자

#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;

long map[50][50] = { 0, };
vector<pair<long, long>> homeV;
vector<pair<long, long>> ChickV;
vector<vector<long>> V;
vector<long> curPath;

long N, M;

long distance(pair<long,long> home, pair<long,long> chick) {
	return (long)(abs(chick.first - home.first) + abs(chick.second - home.second));
}

void Combination(vector<long> arr,vector<long> comb, long r, long index, long depth)
{
	if (r == 0)
	{
		V.push_back(comb);
	}
	else if (depth == arr.size())  // depth == n // 계속 안뽑다가 r 개를 채우지 못한 경우는 이 곳에 걸려야 한다.
	{
		return;
	}
	else
	{
		// arr[depth] 를 뽑지 않은 경우
		Combination(arr, comb, r, index, depth + 1);

		// arr[depth] 를 뽑은 경우
		comb.push_back(arr[depth]);
		Combination(arr,comb, r - 1, index + 1, depth + 1);

		
	}
}

long shortCut() {	
	long _count = 0;
	long ret;
	for (long i = 0; i < homeV.size(); i++) {
		ret = 987654321;
		for (long j = 0; j < ChickV.size(); j++) {			
			ret = min(ret, distance(homeV[i], ChickV[j]));
		}
		_count += ret;
	}
	return _count;
}
// 무시무시한 3중 for문... 그래도 N 50에 M 13이니 너무 쫄 필요는 없을듯하다.
// 50개의 집이 직접 13개의 점포를 확인해도  650밖에 안된다. 테스트 케이스가 13개중 4개를 뽑는다 해도 백만도 안된다.
long compShortCut(long testCase) {	
	long ret = 987654321;
	long curMin;
	for (long i = 0; i < testCase; i++) {				
		long _count = 0;
		for (long j = 0; j < homeV.size(); j++) {
			curMin = 987654321;
			for (long k = 0; k < V[i].size(); k++) {
				curMin = min(curMin, distance(homeV[j], ChickV[V[i].at(k)]));
			}
			_count += curMin;
		}
		ret = min(_count, ret);
	}
	return ret;
}


int main()
{
	ios::sync_with_stdio(false);
	cin.tie(NULL);
	cin >> N >> M;
	for (long i = 0; i < N; i++) {
		for (long j = 0; j < N; j++) {
			cin >> map[i][j];
			if (map[i][j] == 1) {
				homeV.push_back(pair<long,long>(i,j));				
			}
			else if (map[i][j] == 2) {
				ChickV.push_back(pair<long, long>(i, j));
			}
		}
	}
	long ans =0;
	if (M >= ChickV.size()) {//M과 현재 치킨점포수가 같으면 그냥 숏컷함수로 바로 찾는다. 이건 쉽다.
		ans = shortCut();
		cout << ans;
	}
	else {// 킹치만, 다를 경우 먼저 치킨점포수를 M의 개수로 뽑아서 shortcut을 돌려야 한다.
		vector<long> combi;
		vector<long> arr1;
		for (long i = 0; i < ChickV.size(); i++) {
			arr1.push_back(i);
		}
		// 가장 기본적인 조합 함수이다. 재귀 호출로 모든 조합을 찾는다.
		Combination(arr1, combi, M, 0,0);
		// 모든 조합에 대해 shortcut과 같은 함수를 돌려 최소 치킨거리를 찾고 그중에서 또 최소값을 찾는다.
		long ans = compShortCut(V.size());
		cout << ans;
	}

	

	return 0;

}

2. 작동 원리

• 자세한 내용은 주석을 참고하면 되겠다.

일단 현존하는 모든 조합을 찾는다. 거기에 최소가 되는 치킨집 거리를 3중 for문을 돌려서 찾는다.
매우 간단하고 무식한 방법이지만 가장 직관적인 방법이라 생각된다.

3. 배운 점

• 이번에도 또 출력에서 실수해서 몇번 실패가 떴다. 항상 출력부분을 잘 생각하자
• 너무 어렵게 생각하지 말자. 물론 최적화가 필요한 문제이면 더욱 최적화를 해서 내야하지만 굳이 그렇게까지 하지 않아도 생각보다 컴퓨터는 빠르다.
• 직관적으로 짜고 나서 추후에 업그레이드를 하는 방식으로 천천히 생각하자. 처음부터 원대한 알고리즘을 떠올리기란 쉽지 않다.