[BOJ] 15686번 : 치킨 배달

1. problem : 

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

 

2. solution 1 :

#include <bits/stdc++.h>
using namespace std;
#define X first
#define Y second 
int n, m;
int board[52][52]; 
vector<pair<int, int>> house;
vector<pair<int, int>> all_chicken;
vector<pair<int, int>> cho_chicken;
bool isUsed[15];
int mn_dist = 15000; 

void chickenDist(int cnt, int target_cnt) {
	if (target_cnt == cnt) {
		int dist_sum = 0;
		for (int i = 0; i < house.size(); i++) {
			int house_mn_dist = 200;
			for (int j = 0; j < cho_chicken.size(); j++) {
				int dist = 0;
				int diff_x = abs(house[i].X - cho_chicken[j].X);
				int diff_y = abs(house[i].Y - cho_chicken[j].Y);
				dist += diff_x;
				dist += diff_y;
				house_mn_dist = min(house_mn_dist, dist);
			}
			dist_sum += house_mn_dist;
		}
		mn_dist = min(mn_dist, dist_sum);
	}
	for (int i = 0; i < all_chicken.size(); i++) {
		if (!isUsed[i]) {
			isUsed[i] = true; 
			cho_chicken.push_back({ all_chicken[i].X,all_chicken[i].Y }); 
			chickenDist(cnt + 1, target_cnt); 
			isUsed[i] = false;
			cho_chicken.pop_back();
		}
	}

}

int main(void) {
	ios::sync_with_stdio(0);
	cin.tie(0);
	cin >> n >> m;
	
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < n; j++) {
			cin >> board[i][j];
			if (board[i][j] == 1) house.push_back({ i,j });
			else if (board[i][j] == 2) all_chicken.push_back({ i,j });
		}
	}
	chickenDist(0, m);
	cout << mn_dist << '\n';
}

실패한 코드 , 시간 초과가 났다. 

 

3. solution 2 :

// Authored by : BaaaaaaaaaaarkingDog
// Co-authored by : -
// http://boj.kr/445279200beb4050ac92ffc9dc68d68b
#include <bits/stdc++.h>
using namespace std;

#define X first
#define Y second

int board[55][55];
int n, m;
vector<pair<int,int>> chicken;
vector<pair<int,int>> house;

int main(void) {
  ios::sync_with_stdio(0);
  cin.tie(0);
  cin >> n >> m;
  for(int i = 0; i < n; i++){
    for(int j = 0; j < n; j++){
      cin >> board[i][j];
      if(board[i][j] == 1) house.push_back({i, j});
      if(board[i][j] == 2) chicken.push_back({i, j});      
    }
  }
  vector<int> brute(chicken.size(), 1);
  fill(brute.begin(), brute.begin() + chicken.size() - m, 0); // 앞의 chicken.size() - m 칸은 0, 뒤의 m칸은 1
  int mn = 0x7f7f7f7f; // 답을 저장할 변수
  do{
    int dist = 0; // 도시의 치킨 거리를 저장할 변수
    for(auto h : house){
      int tmp = 0x7f7f7f7f; // 집의 치킨 거리를 저장할 변수
      for(int i = 0; i < chicken.size(); i++){
        if(brute[i] == 0) continue;      
        tmp = min(tmp, abs(chicken[i].X - h.X) + abs(chicken[i].Y - h.Y)); // 집의 치킨 거리 갱신
      }
      dist += tmp;
    }
    mn = min(mn, dist);
  }while(next_permutation(brute.begin(), brute.end()));
  cout << mn;
}

source code 출처 : https://github.com/encrypted-def/basic-algo-lecture/blob/master/0x0D/solutions/15686.cpp

basic-algo-lecture/0x0D/solutions/15686.cpp at master · encrypted-def/basic-algo-lecture

 

next_permutation을 이용한 코드