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

문제 링크

---

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

15686번: 치킨 배달

 

접근 방법

---

전체적인 순서는 이렇다.

(1) 입력받을 때 모든 치킨집의 좌표 vector에 저장

(2) 저장한 치킨집 vector를 백트래킹하며 가능한 치킨집의 모든 조합에 대하여 치킨거리 계산 후 최솟값 반환

 

총 K개의 치킨집 중에서 M개 (M<=K)의 치킨집을 뽑은 뒤, 모든 도시에 대해서 뽑은 치킨집과의 치킨거리를 계산한다. 그리고 치킨 거리의 합이 최소인 M에서의 치킨 거리를 출력하는 문제이다.

최대 13개의 치킨집에서 최대 M개까지 뽑아서 최소 치킨 거리를 계산하므로, '조합'의 문제이다.

따라서 백트래킹을 하면서 가능한 치킨집의 모든 조합에 대하여 치킨 거리를 계산한 뒤, 최소 치킨 거리를 출력하면 된다.

백트래킹을 오랜만에 보니 기억이 잘 안나서 이전에 짜놓았던 조합을 참고하였다.

 

소스 코드

---

#include <vector>
#include <climits>
#include <cstring>
#include <iostream>
#include <algorithm>
#define MAX 51
using namespace std;
typedef struct coord {
	int y, x;
};
int N, M, map[MAX][MAX], cache_dist[MAX]; // cache_dist[i] : i번째 집의 최소 치킨 거리
vector<coord> chicken, house, selected;
const int INF = 99999999;

int dist(coord& c1, coord& c2) {
	return abs(c1.y - c2.y) + abs(c1.x - c2.x);
}

// h번째 집에 대해서 모든 치킨집과의 거리 계산. 그 중 최소 거리만 남김
int cal_chicken_dist() {
	int ret = 0;
	for (int h = 0; h < house.size(); ++h) {
		int chicken_dist = INF;
		for (int i = 0; i < selected.size(); ++i) {
			chicken_dist = min(chicken_dist, dist(selected[i], house[h]));
		}
		ret += chicken_dist;
	}
	return ret;
}

// 모든 치킨집의 가능한 조합에 대해서 최소 치킨 거리 계산
int nCm(int count, int prev) {
	if (count == M) {
		return cal_chicken_dist();
	}

	int ret = INT_MAX;
	for (int i = prev + 1; i < chicken.size(); ++i) {
		selected.push_back(chicken[i]);
		ret = min(ret, nCm(count + 1, i));
		selected.pop_back();
	}
	return ret;
}

// 최소 M개의 치킨집은 존재
int main() {
	ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
	cin >> N >> M;
	for (int i = 0; i < N; ++i) {
		for (int j = 0; j < N; ++j) {
			cin >> map[i][j];
			if (map[i][j] == 1)
				house.push_back({ i, j });
			else if (map[i][j] == 2)
				chicken.push_back({ i, j });
		}
	}
	cout << nCm(0, -1);
	return 0;
}

개발 환경 : VS2019

질문, 지적 환영합니다!