백준 15686번 | 치킨 배달 (C++ 풀이)

  문제  

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

15686번: 치킨 배달

---

  풀이  

• 사용 알고리즘 : 완전 탐색 + 백트래킹

삼성 SW역량테스트 문제였네요.

저는 일단 완전탐색 + 백트래킹 + 약간의 그리디한 생각으로 풀었습니다.

​

먼저 문제 해석을 잘 해야 합니다.

주어진 치킨집 중에서 최대 M개를 선택하고, 도시의 치킨 거리의 최소를 구하라고 합니다.

여기서 생각해볼만 한 것은, 치킨집을 최대 M개 선택하라 하였으니, 1개부터 M개까지 고를 수 있는 치킨집의 모든 조합을 고려해야 하는가? 입니다.

이때 중요한 것은 우리는 결국 도시 치킨 거리의 "최소"를 구해야 한다는 사실이죠. 직관적으로 생각해봤을 때, 치킨집이 많다고 해서 치킨 거리의 최소를 구하는데 손해 볼 것은 없습니다. 오히려 치킨집이 많으면 집의 입장에서는 더 가까운 치킨집이 존재할 확률이 올라가겠죠. 이득은 아닐 수도 있지만, 적어도 손해는 아니다 라는 사실이 이 문제를 조금 더 간단하게 만듭니다. (물론 입력으로 들어오는 값 자체가 작기 때문에 가능합니다.)

따라서 이 문제는 이렇게 바뀝니다.

주어진 치킨집 중에서 M개를 선택하고, 이때의 도시 치킨 거리의 최소를 구하라.

​

이제 문제가 간단해졌으니 풀이를 생각해봅시다.

1. 치킨집 중 M개를 선택해야 하므로 여러 가지 가능한 모든 조합을 만들어 봐야 합니다. 이는 백트래킹을 이용하여 적절히 구현해주면 됩니다.

2. 치킨집의 조합을 만들었다면 각 경우들에 대해서 집들의 치킨 거리를 구해줍니다.

3. 집들의 치킨 거리를 구했다면 이를 모두 더해서 도시의 치킨 거리를 구합니다.

4. 치킨집의 가능한 조합이 남아있다면 반복해서 도시의 치킨 거리를 구하고 최솟값을 갱신해줍니다.

---

  코드  

#include <bits/stdc++.h> 
using namespace std;
const int INF = 2e9;
const int inf = 1e9;

struct a{
	int x;
	int y;
};

vector<a> tmpV;
vector<a> home;
vector<a> chicken;
int homeDistance[101];
int ans = INF;

void checkDistance(int m, int homeSize) {
	for (int i = 0; i < homeSize; i++) {
		homeDistance[i] = INF;
	}
	
	for (int i = 0; i < homeSize; i++) {
		for (int j = 0; j < m; j++) {
			homeDistance[i] = min(homeDistance[i], abs(home[i].x - tmpV[j].x) + abs(home[i].y - tmpV[j].y));
		}
	}
	int summ = 0;
	for (int i = 0; i < homeSize; i++) {
		summ += homeDistance[i];
	}
	ans = min(ans, summ);
}

void go(int m, int cnt, int idx, int homeSize, int chickenSize) {
	if (m == cnt) {
		checkDistance(m, homeSize);
		return;
	}
	
	for (int i = idx; i < chickenSize; i++) {
		tmpV.push_back({chicken[i].x, chicken[i].y});
		go(m, cnt + 1, i + 1, homeSize, chickenSize);
		tmpV.pop_back();
	}
}

int main(void){
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	
	for (int i = 0; i < 101; i++) {
		homeDistance[i] = INF;
	}
	
	int n, m;
	cin >> n >> m;
	
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < n; j++) {
			int k;
			cin >> k;
			if (k == 1) {
				home.push_back({i, j});
			}
			else if (k == 2) {
				chicken.push_back({i, j});
			}
		}
	}
	
	int homeSize = home.size();
	int chickenSize = chicken.size();
	
	go(m, 0, 0, homeSize, chickenSize);
	
	cout << ans;
	return 0;
}