BOJ-15686 치킨 배달

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

문제 소개

N * N 크기의 도시의 정보와 M이 주어진다.

도시의 정보는 0, 1, 2로 이루어져 있고, 0은 빈 칸, 1은 집, 2는 치킨집을 의미한다.

치킨 거리는 집과 가장 가까운 치킨집 사이의 거리이며, 임의의 두 칸 (r1, c1)과 (r2, x2) 사이의 거리는 |r1 - r2| + |c1 - c2|로 구한다.

도시의 치킨 거리는 모든 집의 치킨 거리의 합이다.

도시에 있는 치킨집 중에서 최대 M개를 골라 도시의 치킨 거리가 최소가 되도록 하자.

문제 풀이

도시의 정보를 입력받을 때 1인 경우와 2인 경우에 각각 house와 chicken라는 vector에 좌표를 저장하였다.

다음으로는 target과 idx라는 vector를 선언하여 치킨집 중 m개를 고르기 위한 조합을 구하기 위해 사용하였다.

함수 get_dist()는 두 좌표 사이의 거리를 구하는 함수이다. do-while 문 내부에서 사용하였다.

치킨집을 고르는 각 경우의 수에 대하여 도시의 치킨 거리에 해당하는 sum을 구한다.

최종적으로 도시의 치킨 거리의 최솟값인 chicken_dist를 출력한다.

코드

#include <iostream>
#include <vector>
#include <cmath>
#include <algorithm>
#include <numeric>

typedef std::pair<int, int> coord;

int get_dist(coord x, coord y) {
	return abs(x.first - y.first) + abs(x.second - y.second);
}

int main() {
	using namespace std;
	cin.tie(NULL);
	ios_base::sync_with_stdio(false);

	int n, m;
	cin >> n >> m;

	vector<coord> house;
	vector<coord> chicken;
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < n; j++) {
			int t;
			cin >> t;
			if (t == 1) {
				house.push_back({ i, j });
			}
			if (t == 2) {
				chicken.push_back({ i, j });
			}
		}
	}

	// chicken.size() 중 m개 뽑기

	vector<int> target;
	for (int i = 0; i < chicken.size(); i++) {
		target.push_back(i);
	}

	vector<bool> idx(chicken.size() - m, 0);
	for (int i = 0; i < m; i++) {
		idx.push_back(1);
	}

	int chicken_dist = n * n * house.size();

	do {
		vector<int> min_dist(house.size(), n * n);
		for (int i = 0; i < chicken.size(); i++) {
			if (idx[i]) {
				for (int j = 0; j < house.size(); j++) {
					int dist = get_dist(chicken[i], house[j]);
					min_dist[j] = dist < min_dist[j] ? dist : min_dist[j];
				}
			}
		}
		int sum = accumulate(min_dist.begin(), min_dist.end(), 0);
		chicken_dist = sum < chicken_dist ? sum : chicken_dist;
	} while (next_permutation(idx.begin(), idx.end()));

	cout << chicken_dist << '\n';

	return 0;
}