[1일차] 알고리즘 기초 L - 15686 : 치킨 배달

골드 Ⅴ

 

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

struct Point {
	int x, y;
};

int N, M;
vector<Point> chickPoint;
vector<Point> housePoint;
vector<int> chickDiss;
int dosiMinchickDis = 10000000;

vector<int> nCm;
void backtracking(int start) {

	//m개의 치킨집이 골라졌을 때
	if (nCm.size() == M) {

		//집들의 치킨거리 구하기
		int cnt = 0;
		for (auto house : housePoint) {
			int minChickDis = 1000000;
			//m개의 치킨 집 중 최소거리 구하기
			for (auto chickIdx : nCm) {
				int chickDis = 0;
				chickDis += abs(chickPoint[chickIdx].x - house.x);
				chickDis += abs(chickPoint[chickIdx].y - house.y);
				if (chickDis < minChickDis) minChickDis = chickDis;
			}
			//printf("%d번째 집의 치킨거리 : %d\n", cnt, minChickDis);
			cnt++;
			chickDiss.push_back(minChickDis);
		}

		//도시의 치킨거리 구하기
		int dosiChickDis = 0;
		for (auto i : chickDiss) dosiChickDis += i;
		//printf("도시의 치킨거리: %d\n", dosiChickDis);
		chickDiss.clear();
		//도시의 치킨거리 최소값 찾기
		if (dosiChickDis < dosiMinchickDis) dosiMinchickDis = dosiChickDis;
		return;
	}
	
	//치킨집의 개수 중에서
	for (int i = start; i < chickPoint.size(); i++) {
		nCm.push_back(i);
		backtracking(i + 1);
		nCm.pop_back();
	}
}

int main() {
	scanf("%d%d", &N, &M);

	int tmp;
	for (int i = 0; i < N; i++) {
		for (int j = 0; j < N; j++) {
			scanf("%d", &tmp);
			if (tmp == 1) {
				housePoint.push_back({ i, j });
			}
			else if (tmp == 2) {
				chickPoint.push_back({ i, j });
			}
		}
	}

	backtracking(0);
	printf("%d", dosiMinchickDis);
}

 

조합 + 브루트포스

 

이게.. m개의 치킨집을 고르고?

골라진 치킨집에 대해서 집 당 치킨거리를(최소를 구해야함 치킨거리의 정의가 최소...) 구하고?

구해진 집 당 치킨거리를 모든 집에 대하여 다 더하면 도시의 치킨 거리가 되는거고

이 도시의 치킨거리 중에서 최소 값을 찾는거라

알고리즘이 어려운건 아닌데.. 자꾸 최소? 이게 최소? 여기서 최소? 엥?

하게 돼서 오래걸림