문제
코드
#include <bits/stdc++.h>
using namespace std;
int n, m;
int arr[50][50];
vector<pair<int, int> > chicken;
vector<pair<int, int> > house;
// 치킨 거리의 합을 계산하는 함수
int getSum(vector<pair<int, int> > candidates) {
int result = 0;
// 모든 집에 대하여
for (int i = 0; i < house.size(); i++) {
int hx = house[i].first;
int hy = house[i].second;
// 가장 가까운 치킨 집을 찾기
int temp = 1000000000;
for (int j = 0; j < candidates.size(); j++) {
int cx = candidates[j].first;
int cy = candidates[j].second;
temp = min(temp, abs(hx - cx) + abs(hy - cy));
}
// 가장 가까운 치킨 집까지의 거리를 더하기
result += temp;
}
// 치킨 거리의 합 반환
return result;
}
int main(void) {
cin >> n >> m;
for (int r = 0; r < n; r++) {
for (int c = 0; c < n; c++) {
cin >> arr[r][c];
if (arr[r][c] == 1) house.push_back({r, c}); // 일반 집
else if (arr[r][c] == 2) chicken.push_back({r, c}); // 치킨집
}
}
// 모든 치킨 집 중에서 m개의 치킨 집을 뽑는 조합 계산
vector<bool> binary(chicken.size()); //치킨집 개수만큼 크기 설정
fill(binary.end() - m, binary.end(), true); //m개만큼만 값을 0으로 설정,나머지 1
// 치킨 거리의 합의 최소를 찾아 출력
int result = 100000000;
do {
vector<pair<int, int> > now;
for (int i = 0; i < chicken.size(); i++) {
if (binary[i]) {
int cx = chicken[i].first;
int cy = chicken[i].second;
now.push_back({cx, cy});
}
}
result = min(result, getSum(now));
} while(next_permutation(binary.begin(), binary.end()));
cout << result << '\n';
}
'코테 > 구현' 카테고리의 다른 글
[java] 프로그래머스 스쿨 모의고사 (0) | 2023.12.27 |
---|---|
[C/C++] 프로그래머스스쿨 외벽 점검, 구현 (0) | 2023.02.26 |
[C/C++] 프로그래머스 스쿨 기둥과 보, 구현 (0) | 2023.02.26 |
[C/C++] 프로그래머스스쿨 자물쇠와 열쇠, 구현 (0) | 2023.02.26 |
[C/C++] 백준 3190, 구현 (0) | 2023.02.18 |