• 문제

    1

  • 고민

    처음에는 배열이 입력으로 주어지기 때문에 배열에 값을 넣고 2중 for문을 돌며 각 치킨 거리를 계산하려고 하였다. 집과 치킨집의 위치는 고정인데 굳이 그럴필요가 있나 생각이 들어 집과 치킨집의 좌표를 저장하는 배열을 만들고 두 배열간의 원소끼리 비교하는 방법을 택하기로 했다. 최대 M개의 치킨집과 각 집간의 치킨 거리의 최소의 값을 더한 값이 최소가 될 때 그 값을 출력하면 되므로, 치킨집을 1개 ~ M개 까지의 조합을 모두 따지면서 구했다. 최단 치킨 거리와 정답의 최소값을 구하기전 초기화 값을 적당히 큰 수로 결정했는데, 치킨 거리는 어차피 양수이므로 -1로 초기값을 잡는게 더 좋은 방법일 것 같다.

  • 코드

    // https://www.acmicpc.net/problem/15686
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
  
int n, m;
vector<pair<int, int> > h;
vector<pair<int, int> > c;
  
int main() {
	ios::sync_with_stdio(false);
	cin >> n >> m;
	for (int i = 1; i <= n; i++) {
		for (int j = 1; j <= n; j++) {
			int temp = 0;
			cin >> temp;
			if (temp == 2) {
				c.push_back(make_pair(i, j));
			}
			else if (temp == 1) {
				h.push_back(make_pair(i, j));
			}
		}
	}
  
	int ans = 987654321;
	for (int k = 1; k <= m; k++) {
		vector<int> v;
		for (int l = 0; l < k; l++) {
			v.push_back(1);
		}
		for (int l = k; l < c.size(); l++) {
			v.push_back(0);
		}
		do {
			int min_sum = 0;
			for (int i = 0; i < h.size(); i++) {
				int min_distance = 987654321;
				for (int j = 0; j < c.size(); j++) {
					if (v[j] == 1) {
						int x = h[i].first - c[j].first;
						int y = h[i].second - c[j].second;
						int temp_distance = (x > 0 ? x : -x) + (y > 0 ? y : -y);
						min_distance = min(min_distance, temp_distance);
					}
				}
				min_sum += min_distance;
			}
			ans = min(ans, min_sum);
		} while (prev_permutation(v.begin(), v.end()));
		v.clear();
	}
  
	cout << ans << '\n';
	return 0;
}