[BOJ] 15686번 | 치킨 배달 (C++)

🔗문제 보러가기

15686번: 치킨 배달

 

🧑🏻‍💻풀이 과정

보자마자 조합(Combination)이 떠오르긴 했는데, 이게 정말 단순히 조합만으로 풀릴까?... 시간 초과가 걸리진 않을까?, 중복 계산을 줄일 수 있는 방법이 없을까? 고민을 했는데, 쓸 데 없는 고민이었단 걸 깨달았습니다.

아무래도 집의 개수가 2N개를 넘지 않고, N과 M의 개수가 그렇게 크지 않기 때문인 것 같네요. 게다가, 집과 치킨 집만 사용하니 \( N \times N \) 크기를 모두 탐색할 필요가 없는 점도 한 몫하는 것 같습니다.

 

 

서론이 길었네요. 아무튼 제 풀이는 다음과 같습니다.

1. 도시 내의 집 좌표와 치킨 집 좌표를 얻어와, 각각 배열에 저장한다.
2. 조합을 통해, 치킨 집들 중 M개를 선택한다.
3. M개를 선택했다면, 각각의 집에 대해, M개의 치킨 집들 중 가장 가까운 거리를 선택하여 합산한다. (치킨 거리 구하기)
   • 구하는 과정에서 합산 값이 최소 도시 치킨 거리보다 커진다면, 더 이상 계산할 필요가 없으므로 종료
   • 종료 후, 다음 조합으로 넘어가서 다시 3번 과정을 진행한다. 
4. 모든 치킨 거리를 다 합산했다면, 최소 도시 치킨 거리와 비교하여 더 작은 것으로 갱신한다.
5. 모든 비교를 다 완료했다면, 답을 출력한다.

 

✏️소스 코드 및 결과

#include <iostream>
#include <vector>
using namespace std;
using Position = pair<int, int>;

class City
{
public:
	City(int N, int M);
	int GetMinChickenStreet();

private:
	int GetDistance(const Position& p1, const Position& p2) { return abs(p1.first - p2.first) + abs(p1.second - p2.second); }
	void GetMinChickenStreet(vector<int>& selectedChickens, int currentIdx);

private:
	const int HOUSE = 1;
	const int CHICKEN = 2;
	const int INIT_VALUE = 1000000000;

	vector<Position> _houses;
	vector<Position> _chickens;

	int _minChickenStreet = INIT_VALUE;
	int _M;
};

City::City(int N, int M)
{
	_M = M;

	for (int row = 0; row < N; row++)
	{
		for (int col = 0; col < N; col++)
		{
			int information;
			cin >> information;

			if (information == HOUSE)
				_houses.emplace_back(row, col);
			else if (information == CHICKEN)
				_chickens.emplace_back(row, col);
		}
	}
}

void City::GetMinChickenStreet(vector<int>& selectedChickens, int currentIdx)
{
	if (selectedChickens.size() == _M)
	{
		int sum = 0;
		for (int hi = 0; hi < _houses.size(); hi++)
		{
			int minDistance = INIT_VALUE;
			for (const int& ci : selectedChickens)
				minDistance = min(minDistance, GetDistance(_houses[hi], _chickens[ci]));
			
			sum += minDistance;
			if (sum > _minChickenStreet)
				return;
		}

		_minChickenStreet = min(_minChickenStreet, sum);
		return;
	}

	for (int i = currentIdx; i < _chickens.size(); i++)
	{
		selectedChickens.emplace_back(i);
		GetMinChickenStreet(selectedChickens, i + 1);
		selectedChickens.pop_back();
	}
}

int City::GetMinChickenStreet()
{
	vector<int> selectedChickens;
	GetMinChickenStreet(selectedChickens, 0);
	return _minChickenStreet;
}

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

	int N, M;
	cin >> N >> M;

	City city(N, M);
	cout << city.GetMinChickenStreet();
	return 0;
}