[15686] 치킨 배달

---

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

15686번: 치킨 배달

 

 

무엇을 구현해야 하는지 한참을 헤맸다.

문제에서 최대 M개만 남겨두고 폐업한다는 말을 이해하지 못해서 삽질하다가 구글링의 힘을 빌렸다.

 

총 치킨집의 개수는 M과 같거나 M보다 크다고 본문에 나와있다. 따라서 총 치킨집의 개수 중에서 M개만 뽑아야 하는 조합 문제이다. 이걸 몰라서 1시간을 삽질 굳~

 

그럼 조합은 혼자서 구현했냐고 물으신다면~ 그러지 못했다.

처음에는 모든 경우의 수를 구조체 배열에 담아서 해결하면 되지 않을까 했는데 너무 복잡하고 어리석은 생각 같아서 30분 고민하다가 그만뒀다.

 

결론은 아래의 코드이다.

void selectChicken(int index, int count) {
	if (count == M) {
		distance(); // 조합이 모두 뽑혔으면 거리를 구함
	}
	else {
		// 아직 덜 뽑혔다면
		for (int i = index; i < chicken.size(); i++) {
			if (chicken[i].isvisited == false) {
				chicken[i].isvisited = true; // 선택된 기준은 true로
				selectChicken(i + 1, count + 1); // 다음 index부터 접근하여 조합을 계속해서 구함
				chicken[i].isvisited = false;
			}
		}
	}
}

chicken이라는 vector를 만든다. 다만 자료형이 구조체이다. 

struct C {
	int x; int y; bool isvisited = false;
};

x와 y는 해당 치킨집의 좌표이고, 조합을 구현해야 하기 때문에 isvisited 변수를 추가해주었다.

 

그 다음 선택된 치킨집은 true로 바꿔주고 다음 index부터 접근하여 count를 1 증가시켜준다. 

그렇게 count가 M에 다다르면 해당 치킨집들의 최소 거리를 구한다.

void distance() {	
	// 각 집에 대한 치킨집의 최소거리 구함
	int sum = 0;
	for (int i = 0; i < house.size(); i++) {
		int minimum = MAX_INT;
		for (int j = 0; j < chicken.size(); j++) {
			if (chicken[j].isvisited == true) {
				// 선택된 치킨집이라면 거리를 구함
				int dist= abs(chicken[j].x - house[i].x) + abs(chicken[j].y - house[i].y);
				minimum = (dist < minimum) ? dist : minimum;				
			}
		}
		sum += minimum; // 해당 집에서 제일 최소 거리인 치킨집 더함
	}

	min_sum = (sum < min_sum) ? sum : min_sum;
}

MAX_INT는 2,147,483,647이다. 대충 1000으로 초기화해도 맞겠지? 하면서 1000을 넣었는데 틀렸다. 주의하자!

각 집에 대한 최소 치킨집의 거리를 구하는 코드이다.

선택된 치킨집이라면 일단 거리를 구하고 이전의 최솟값보다 작은지 비교한다음 minimum 변수에 넣어준다.

그렇게 minimum이 갱신되면 해당 집에서 제일 최소 거리의 치킨 거리가 나올 것이므로 이를 sum에 더해준다.

그렇게 더해준 sum은 다시 모든 경우의 수들에 대해 최솟값인지 비교하여 min_sum에 넣는다.

 

 

정말 삼성은 어려운 존재구나

#include <iostream>
#include <algorithm>
#include <vector>
#define MAX_INT 2147483647
using namespace std;

int N, M;

struct Point {
	int x; int y;
};

struct C {
	int x; int y; bool isvisited = false;
};

vector<Point> house;
vector<C> chicken;
int min_sum = MAX_INT; // 도시의 치킨 거리

/*
조합 문제
최대 M개 고른다 -> 조합

조합으로 M개의 치킨집을 뽑는다
각 집에서 M개의 치킨집까지의 거리 중 최솟값들을 구하여 더한다
가장 최소거리 합이 나오는 조합의 거리 값을 구한다
*/

void distance() {	
	// 각 집에 대한 치킨집의 최소거리 구함
	int sum = 0;
	for (int i = 0; i < house.size(); i++) {
		int minimum = MAX_INT;
		for (int j = 0; j < chicken.size(); j++) {
			if (chicken[j].isvisited == true) {
				// 선택된 치킨집이라면 거리를 구함
				int dist= abs(chicken[j].x - house[i].x) + abs(chicken[j].y - house[i].y);
				minimum = (dist < minimum) ? dist : minimum;				
			}
		}
		sum += minimum; // 해당 집에서 제일 최소 거리인 치킨집 더함
	}

	min_sum = (sum < min_sum) ? sum : min_sum;
}

void selectChicken(int index, int count) {
	if (count == M) {
		distance(); // 조합이 모두 뽑혔으면 거리를 구함
	}
	else {
		// 아직 덜 뽑혔다면
		for (int i = index; i < chicken.size(); i++) {
			if (chicken[i].isvisited == false) {
				chicken[i].isvisited = true; // 선택된 기준은 true로
				selectChicken(i + 1, count + 1); // 다음 index부터 접근하여 조합을 계속해서 구함
				chicken[i].isvisited = false;
			}
		}
	}
}

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

	cin >> N >> M;
	for (int i = 1; i <= N; i++) {
		for (int j = 1; j <= N; j++) {
			int input;
			cin >> input;
			// 좌표값 저장
			if (input == 1) {
				// 집이면
				house.push_back({ i,j });
			}
			else if (input == 2) {
				// 치킨집이면
				chicken.push_back({ i,j,false });
			}
		}
	}

	selectChicken(0, 0); // 치킨집 고른다

	cout << min_sum;	
}