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

 

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

 

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

15686번: 치킨 배달

---

 

 

해결전략

 

백트래킹, Backtracking

 

---

 

 

정답 코드

 

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

int n, m; // n: 도시 크기, m: 선택할 치킨집의 개수
int answer = 2147000000; // 최소 치킨 거리를 저장할 변수
vector<vector<int>> v;
vector<pair<int, int>> house, chicken, delevery;
int ch[14]; // 치킨집 체크

int Distance() // 각 집에서 치킨집까지의 거리를 측정하는 함수
{
	int sum = 0;
	for(int i=0; i<house.size(); i++)
	{
		int y = house[i].first;
		int x = house[i].second;
		int d = 2147000000;

		// 각 집의 좌표를 기준으로 선택된 치킨집들과의 거리를 계산하고, 그 중 가장 짧은 거리를 찾아 더해준다.
		for (int j = 0; j < delevery.size(); j++)
		{
			int ny = delevery[j].first;
			int nx = delevery[j].second;
			int dist = abs(ny - y) + abs(nx - x);

			d = min(d, dist);
		}
		sum = sum + d;
	}

	return sum; // 총 치킨 거리를 반환
}

// 치킨집을 선택하는 함수, 조합(Combination)을 사용
// 모든 치킨집 중에서 m개를 선택하는 모든 조합에 대해 최소 치킨 거리를 계산하고, 그 중 가장 작은 값을 찾아 answer에 저장. 이 때, idx는 조합을 구할 때 시작할 인덱스를 의미하고, cnt는 현재까지 선택한 치킨집의 개수를 의미한다.
void Delivery(int idx, int cnt) 
{
	// m개의 치킨집을 모두 선택했을 경우
	if(cnt == m){ 
		answer = min(answer, Distance()); // 최소 치킨 거리를 업데이트
		return;
	}

	for(int i=idx; i<chicken.size(); i++)
	{
		if (ch[i] == 0)
		{
			delevery.push_back(chicken[i]);

			ch[i] = 1;
			Delivery(i, cnt + 1);
			ch[i] = 0;

			delevery.pop_back();
		}
	}
}

int main()
{
	ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);

	cin >> n >> m;
	v.resize(n, vector<int>(n));
	for (int y = 0; y < n; y++) {
		for (int x = 0; x < n; x++) {
			cin >> v[y][x];

			if (v[y][x] == 1) {
				house.push_back({ y, x });
			}
			else if (v[y][x] == 2) {
				chicken.push_back({ y, x });
			}
		}
	}
	
	Delivery(0, 0);

	cout << answer << "\n";

	return 0;
}

 

 

---