백준 15686 (치킨 배달) c++

문제

15686번: 치킨 배달

n * n 배열이 주어지면 0은 무시하고 1은 집의 위치이고 2는 치킨 집입니다.

여기서 최대 m개의 치킨 집만 존재할 수 있는데 치킨 집과 집의 거리가 최소가 되게 하는 거리값을 구하는 문제

입니다.

예를들어 

n = 5 , k = 3 이고 다음과 같은 배열이 주어지면

0 0 1 0 0
0 0 2 0 1
0 1 2 0 0
0 0 1 0 0
0 0 0 0 2

거리의 최솟값은 5입니다.

 

n = 5, k = 2 이고 다음과 같은 배열이 주어지면

0 2 0 1 0
1 0 1 0 0
0 0 0 0 0
2 0 0 1 1
2 2 0 1 2

거리의 최솟값은 10입니다.

 

처음에 감을 못잡았던 문제입니다.

제가 찾은 단서는 치킨 집이 최대 k개 있을 수 있으니까 입력받은 치킨 집의 조합을 생각하면서 

모두 확인해 완전탐색으로 거리의 최솟값을 구해야 하는 것입니다.

구현에는 한계가 있어 구글의 힘을 빌린 문제였습니다.

 

먼저 입력 부분입니다.

vector<pair<int, int>>home;
vector<pair<int, int>>chicken;
int chicken_cnt = 0;

for (int i = 0; i < n; i++) {
	for (int j = 0; j < n; j++) {
		cin >> arr[i][j];
		if (arr[i][j] == 1)
			home.push_back({ i, j });
		if (arr[i][j] == 2) {
			chicken.push_back({ i, j });
			chicken_cnt++;
		}
	}
}

home 벡터에는 집의 위치를 넣어주고 chicken 벡터에는 치킨 집의 위치를 넣어주고 몇개의 치킨 집이

존재하는지 세는 chicken_cnt변수 존재합니다.

 

이제 치킨집의 조합을 살펴보아야 합니다.

만약 치킨집이 5개 주어지고{1, 2, 3, 4, 5} k가 3이면 {1,2,3}과 {2,1,3} 은 똑같은것으로 취급해줘야 합니다.

vector<pair<int, int>>v;
bool check[14];
int ans = MAX;

sol(0, 0);

void sol(int idx, int cnt) {
	if (cnt == m) {
		ans = min(ans, cal());
		return;
	}
	for (int i = idx; i < chicken_cnt; i++) {
		if (check[i])continue;
		check[i] = true;
		v.push_back(chicken[i]);
		sol(i, cnt + 1);
		check[i] = false;
		v.pop_back();
	}
}

 벡터 v에는 조합으로 선택한 치킨집이 k개 들어갈 예정입니다.

check 배열로 몇번째 치킨집이 들어가있는지 체크해줍니다.

 

이제 조합을 통해 k개의 치킨집이 선택되었으면 거리를 계산해줘야 합니다.

int cal() {
	int sum = 0;
	for (int i = 0; i < home.size(); i++) {
		int x = home[i].first;
		int y = home[i].second;
		int d = MAX;
		for (int j = 0; j < v.size(); j++) {
			int xx = v[j].first;
			int yy = v[j].second;
			int dist = abs(x - xx) + abs(y - yy);

			d = min(d, dist);
		}
		sum += d;
	}
	return sum;
}

집의 위치를 기준으로 조합으로 선택된 치킨집을 반복문을 돌려 가장 가까운 거리를 찾아 갱신해주고

sum 변수에 누적해서 더해줍니다.

 

문제에서 최대 k개의 치킨집이라 해서 

만약 k = 3이라면 치킨집 1개, 2개, 3개 각각 따로 생각하다보니 문제를 너무 복잡하게 생각했었습니다.

---

전체 코드입니다.

#include <iostream>
#include <algorithm>
#include <cstring>
#include <vector>
#include <string>
#include <stack>
#include <queue>
#include <deque>
#include <cmath>
#include <map>
#include <set>
#include <tuple>
#define MAX 2100000000
#define inf LONG_MAX
#define big(a, b) a > b ? a : b
using namespace std;
using ll = long long;
using ull = unsigned long long;
vector<pair<int, int>>home;
vector<pair<int, int>>chicken;
vector<pair<int, int>>v;
int arr[51][51];
int n, m;
int chicken_cnt = 0;
bool check[14];
int ans = MAX;
void sol(int idx, int cnt);
int cal();
int main() {
    ios_base::sync_with_stdio(false), cin.tie(NULL), cout.tie(NULL);
    cin >> n >> m;
    
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            cin >> arr[i][j];
            if (arr[i][j] == 1)
                home.push_back({ i, j });
            if (arr[i][j] == 2) {
                chicken.push_back({ i, j });
                chicken_cnt++;
            }
        }
    }
 
    sol(0, 0);
    cout << ans;
 
    return 0;
}
void sol(int idx, int cnt) {
    if (cnt == m) {
        ans = min(ans, cal());
        return;
    }
    for (int i = idx; i < chicken_cnt; i++) {
        if (check[i])continue;
        check[i] = true;
        v.push_back(chicken[i]);
        sol(i, cnt + 1);
        check[i] = false;
        v.pop_back();
    }
}
int cal() {
    int sum = 0;
    for (int i = 0; i < home.size(); i++) {
        int x = home[i].first;
        int y = home[i].second;
        int d = MAX;
        for (int j = 0; j < v.size(); j++) {
            int xx = v[j].first;
            int yy = v[j].second;
            int dist = abs(x - xx) + abs(y - yy);
 
            d = min(d, dist);
        }
        sum += d;
    }
    return sum;
}