백준 15686번 치킨배달 (Brute-Force)

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

15686번: 치킨 배달

 

전체 치킨집중 M개만 뽑아서 가장 작은 도시의 치킨거리를 구해야하므로 브루트포스를 이용하면 쉽게 풀 수 있다.

DFS를 통해 치킨집을 뽑거나 순열을 이용해서 뽑을 수 있는데, 이번에는 순열을 이용해서 구현해보도록 한다.

 

우선 값을 입력받고, 1이면 house vector에 2이면 chicken vector에 값을 대입한다.

무작정 순열을 이용할 순 없고, chicken vector의 index값을 순열을 이용해서 구한 뒤, 이 index 값을 chicken vector에 이용하는 방식이다.

 

이를 위해 임시벡터 v에 치킨 집 개수인 m만큼 1을 대입한다.

먼저 순열은 오름차순으로 출력되므로 sort를 이용해 가장 작은 값으로 정렬한다.

다음으로 while문을 수행하면서 next_permutation을 통해 순열을 구현한다.

예를 들어 치킨집 개수가 5개이고, m이 2개이면 처음에 v vector에는 정렬을 통해 00011 이 대입된다.

next_permutation 명령어를 통해 순열을 수행하면 00011 부터 11000까지 오름차순으로 차례대로 v에 값이 변경된다.

따라서 v에 index가 1인 경우에만 치킨집과 집과의 거리를 계산하여 최소값을 구현하면 답을 도출할 수 있다.

 

<소스코드>

#include<iostream>
#include<vector>
#include<algorithm>

using namespace std;

int n, m;
int a[51][51];
int ans = 0xfffffff;

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

int distance(int hx, int hy, int cx, int cy) {
	return abs(cx - hx) + abs(cy - hy);
}

int main(void) {
	cin >> n >> m;

	for (int i = 0; i < n; i++) {
		for (int j = 0; j < n; j++) {
			cin >> a[i][j];

			if (a[i][j] == 1) {
				house.push_back(make_pair(i, j));
			}
			else if (a[i][j] == 2) {
				chicken.push_back(make_pair(i, j));
			}
		}
	}

	vector<int> v(chicken.size());
	for (int i = 0; i < m; i++) {
		v[i] = 1;
	}
	sort(v.begin(), v.end());

	do {
		int temp = 0;
		for (int i = 0; i < house.size(); i++) {
			int dist = 0xfffffff;

			for (int j = 0; j < chicken.size(); j++) {
				if (v[j] == 1) {
					dist = min(dist, distance(house[i].first, house[i].second, chicken[j].first, chicken[j].second));
				}
			}
			temp += dist;
		}
		ans = min(ans, temp);
	} while (next_permutation(v.begin(), v.end()));

	cout << ans << "\n";

	return 0;
}