백준 - 치킨 배달 (15686) [C++]

이 문제는 구현 문제이다.

 

이 문제에서 시간 복잡도는 13Cm * 2N * m 이다. 

13C6이나 13C7 일 때 1,719로 가장 큰데, 이 때도 약 100만 밖에 되지 않으므로 충분히 1초 안에 풀 수 있다.

 

처음에는 bfs를 생각했으나, 치킨 거리를 수식으로 한번에 알 수 있으므로 시간 복잡도만 늘리는 꼴이었다는 것을 깨달았고 단순히 구현하여 해결할 수 있었다.

 

집과 치킨집을 입력에서 받아 배열로 따로 저장한 뒤, 치킨집에서 M개를 선택해 치킨 거리를 측정하는 방식으로 구현했다.

#include <iostream>
#include <algorithm>
#include <vector>
#include <utility>
using namespace std;

#define MAX 50
#define INF 1000000000

int N, M;
vector<pair<int, int>> house;
vector<pair<int, int>> chicken;

int absolute(int a) {
	if (a < 0) {
		return -a;
	}
	return a;
}

int pick(vector<pair<int, int>> &temp, int index) {
	if (temp.size() == M) {
		// some action
		int result = 0;

		for (pair<int, int> &presentHouse : house) {
			int dist = INF;

			for (pair<int, int> &chick : temp) {
				int presentDist = absolute(chick.first - presentHouse.first)
					+ absolute(chick.second - presentHouse.second);
				
				dist = min(dist, presentDist);
			}

			result += dist;
		}

		return result;
	}

	int result = INF;
	for (int i = index + 1; i < chicken.size(); i++) {
		temp.push_back(chicken[i]);
		result = min(result, pick(temp, i));
		temp.pop_back();
	}

	return result;
}

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

	cin >> N >> M;

	for (int y = 1; y <= N; y++) {
		for (int x = 1; x <= N; x++) {
			int num;
			cin >> num;

			if (num == 1) {
				house.push_back({ y, x });
			} else if (num == 2) {
				chicken.push_back({ y, x });
			}
		}
	}

	vector<pair<int, int>> temp;
	int answer = pick(temp, -1);
	cout << answer << '\n';

	return 0;
}