[백준] (수정)15686 치킨배달 + 순열과 조합(next_permutation)
문제
크기가 N×N인 도시가 있다. 도시는 1×1크기의 칸으로 나누어져 있다. 도시의 각 칸은 빈 칸, 치킨집, 집 중 하나이다. 도시의 칸은 (r, c)와 같은 형태로 나타내고, r행 c열 또는 위에서부터 r번째 칸, 왼쪽에서부터 c번째 칸을 의미한다. r과 c는 1부터 시작한다.
이 도시에 사는 사람들은 치킨을 매우 좋아한다. 따라서, 사람들은 "치킨 거리"라는 말을 주로 사용한다. 치킨 거리는 집과 가장 가까운 치킨집 사이의 거리이다. 즉, 치킨 거리는 집을 기준으로 정해지며, 각각의 집은 치킨 거리를 가지고 있다. 도시의 치킨 거리는 모든 집의 치킨 거리의 합이다.
임의의 두 칸 (r1, c1)과 (r2, c2) 사이의 거리는 |r1-r2| + |c1-c2|로 구한다.
예를 들어, 아래와 같은 지도를 갖는 도시를 살펴보자.
0 2 0 1 0
1 0 1 0 0
0 0 0 0 0
0 0 0 1 1
0 0 0 1 2
0은 빈 칸, 1은 집, 2는 치킨집이다.
(2, 1)에 있는 집과 (1, 2)에 있는 치킨집과의 거리는 |2-1| + |1-2| = 2, (5, 5)에 있는 치킨집과의 거리는 |2-5| + |1-5| = 7이다. 따라서, (2, 1)에 있는 집의 치킨 거리는 2이다.
(5, 4)에 있는 집과 (1, 2)에 있는 치킨집과의 거리는 |5-1| + |4-2| = 6, (5, 5)에 있는 치킨집과의 거리는 |5-5| + |4-5| = 1이다. 따라서, (5, 4)에 있는 집의 치킨 거리는 1이다.
이 도시에 있는 치킨집은 모두 같은 프랜차이즈이다. 프렌차이즈 본사에서는 수익을 증가시키기 위해 일부 치킨집을 폐업시키려고 한다. 오랜 연구 끝에 이 도시에서 가장 수익을 많이 낼 수 있는 치킨집의 개수는 최대 M개라는 사실을 알아내었다.
도시에 있는 치킨집 중에서 최대 M개를 고르고, 나머지 치킨집은 모두 폐업시켜야 한다. 어떻게 고르면, 도시의 치킨 거리가 가장 작게 될지 구하는 프로그램을 작성하시오.
입력
첫째 줄에 N(2 ≤ N ≤ 50)과 M(1 ≤ M ≤ 13)이 주어진다.
둘째 줄부터 N개의 줄에는 도시의 정보가 주어진다.
도시의 정보는 0, 1, 2로 이루어져 있고, 0은 빈 칸, 1은 집, 2는 치킨집을 의미한다. 집의 개수는 2N개를 넘지 않으며, 적어도 1개는 존재한다. 치킨집의 개수는 M보다 크거나 같고, 13보다 작거나 같다.
#include<bits/stdc++.h>
using namespace std;
int n, m;
int arr[14];
vector<pair<int, int>>ch; //치킨집 좌표
vector<pair<int, int>>ho; //집 좌표
vector<int>ans;
//거리계산
int cal(pair<int, int> a, pair<int, int> b) {
return abs(a.first - b.first)+ abs(a.second - b.second);
}
//재귀를 이용한 백트래킹 모든 치킨집의 조합을 찾음
void bt(int k) {
if (k == m+1) {
int dis = INT_MAX;
int sum = 0;
//브루트포스 각 집에서 가장 가까운 치킨집의 거리들의 합을 구함
for (int i = 0; i < ho.size(); i++) {
dis = INT_MAX;
for (int j = 1; j < k; j++) {
int temp = cal(ho[i], ch[arr[j]]);
if (temp<dis) {
dis = temp;
}
}
sum += dis;
}
ans.push_back(sum);
return;
}
for (int i = 0; i < ch.size(); i++) {
if (arr[k - 1] < i) {
arr[k] = i;
bt(k + 1);
}
}
}
int main() {
int x;
cin >> n >> m;
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
cin >> x;
if (x == 1) {
ho.push_back({ i,j });
continue;
}
if (x == 2) {
ch.push_back({ i,j });
continue;
}
}
}
arr[0] = -1;
bt(1);
cout << *min_element(ans.begin(), ans.end());
}골드 5 백트래킹, 브루트포스 문제입니다.
처음 문제를 읽었을 때, bfs를 사용할까 고민을 했었는데 어차피 브루트포스를 이용해 모든 치킨집의 조합을 찾고,
각각의 집에서 치킨거리를 구할 때 단순하게 좌표간 거리만 이용하면 편하게 구현할 수 있을거라 생각했습니다.
따라서 map으로 n*n배열을 사용하지 않았고, 집과 치킨집의 좌표만 벡터로 저장했습니다.
-----------------------------------------------------------------------------------------------------------------------------------------------------------------이전에는 백 트래킹으로 치킨집의 순열을 찾았습니다.
C++ <algorithm>내장함수인 next_permutation을 사용해 보겠습니다.
next_permutation
1.서로 다른 n개를 다양한 방법으로 줄세우는 "순열"이 가능합니다.
2.이를 이용하면 서로다른 n개중 r개를 뽑는 "조합"도 가능합니다.
치킨배달 문제에서는 2번. n개의 치킨집 중, r개를 뽑기가 가능합니다. 따라서 백트래킹 함수를 따로 작성하지 않아도 됩니다.
//기본 사용법
bool next_permutation (Iterator first, Iterator last);
//배열의 처음과 끝을 iterator로 받습니다. 따라서
int arr[10];
vector<int>vec(10);
//인경우 사용법은 다음과 같습니다
next_permutation(arr,arr+10);
next_permutation(vec.begin(),vec.end());만약 컨테이너의 다음 순열이 존재하면 true를 반환, 없으면 false를 반환합니다.
따라서 처음 순열을 초기화 했다면 do-while문으로 모든 순열을 탐색 가능합니다.
int arr[4]={1,0,0,0};
do{
for(int i=0;i<4;i++){
cout<<arr[i];
}
}while(next_permutation(arr,arr+4));
주의할 점이 있습니다.
- 오름차순으로 정렬된 값을 가진 컨테이너로만 사용가능합니다.
- default로 operator < 를 사용해 순열을 생성합니다. 즉 오름차순으로 순열을 생성합니다.
- 중복이 있는 원소들은 중복을 제외하고 순열을 만들어줍니다.
따라서 순열을 구할땐, {1,2,3,4,5}와 같이 오름차 순으로 사용해야하고,
조합을 구할땐, {0,0,0,1,1}와 같이 0을 먼저 쓰고 1을 써야합니다.
이를 이용한 치킨배달의 코드입니다.
#include<iostream>
#include<algorithm>
#include<limits.h>
#include<vector>
using namespace std;
int per[14];
int main() {
int n, m, x;
vector<pair<int, int>>ch, ci;
cin >> n >> m;
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
cin >> x;
if (x == 1) { //집
ci.push_back({ i,j });
}
else if (x == 2) { //치킨집
ch.push_back({ i,j });
}
}
}
int chn = ch.size(), cin = ci.size();
for (int i = m; i < chn; i++) {
per[i] = 1;
} //m개만 false 나머지는 true
int sum, ans = INT_MAX;
do {
//조합을 구할땐 do-while을써보자
sum = 0;
for (int i = 0; i < cin; i++) {
//모든 도시에대해
int temp = INT_MAX;
for (int j = 0; j < chn; j++) {
//모든 치킨집에대해 per배열 순회, m개중 가장 가까운 치킨집 하나 거리를 구해야함
if (!per[j])
temp = min(temp, abs(ci[i].first - ch[j].first) + abs(ci[i].second - ch[j].second));
}
sum += temp;
}
ans = min(ans, sum);
} while (next_permutation(per, per + chn));
cout << ans;
}