BOJ 15686 치킨배달

초기 아이디어

딱맞는 알고리즘이 별다르게 방법이 안 떠오를는 완전탐색이 먼저 떠오른다. 이럴 때는 치킨집의 최대 개수가 13 인것도 하나의 힌트가 된다. 이 이상 넘어가면 조합의 개수가 너무 커지기 때문이다.

 

재귀적으로 치킨집의 조합을 만들고 마지막에 최소 거리를 계산하는 식으로 정답을 찾았는데, 이전에 푼적이 있던 문제였다. 그때 참 최적화를 잘 해놓았는데, 벡터 배열에 모든 경우의 수를 담아내고 차례로 이걸 꺼내서 최소거리를 만들어내는 방식이었다. 이번에는 비트마스킹을 써서 개선해 보았다. 사용하는 메모리가 더 적어졌다.

 

문제풀이

조합 벡터배열 이용

#include<bits/stdc++.h>
using namespace std;

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

void combi(int start, vector<int> b){
	if(b.size() == m){
		chickenList.push_back(b);
		return;
	}
	
	for(int i=start;i<chicken.size();i++){
		b.push_back(i);
		combi(i+1,b);
		b.pop_back();
	}
}

int main(){	
	cin >> n >> m;
	int ret = 987654;
	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({i,j});
			if(a[i][j]==2) chicken.push_back({i,j});	
		}
	}
	vector<int> a;
	combi(0, a);
	for(auto cList : chickenList){
		int sum = 0;
		for(auto i : house){
			int dist = 98765;
			for(auto j : cList){
				dist = min(dist, abs(i.first-chicken[j].first) + abs(i.second-chicken[j].second));
			}
			sum+=dist;
		}
		ret = min(ret, sum);
	}
	cout << ret << "\n";
}

조합 비트마스킹 이용

#include<bits/stdc++.h>
using namespace std;

int n, m, ans = 98765;
vector<pair<int, int>> chiken;
vector<pair<int, int>> house;
vector<int> masks;

void solve(int pos, int mask, int dept){
    if(dept == m){
        masks.push_back(mask);
        return;
    }
    for(int i=pos;i<=chiken.size();i++){
        mask += 1<<i;
        solve(i+1, mask, dept+1);
        mask -= 1<<i;
    }
}

int main(){
    cin >> n >> m;
    for(int i=0;i<n;i++){
        for(int j=0;j<n;j++){
            int k;
            cin >> k;
            if(k == 1) house.emplace_back(i,j);
            if(k == 2) chiken.emplace_back(i,j);
        }
    }
    solve(1, 0, 0);
    for(auto mask : masks){
        int ret = 0;
        for(auto h:house){
            int dis = 987665;
            for(int i=1;i<=chiken.size();i++){
                if(mask & 1<<i){
                    dis = min(dis, abs(h.first - chiken[i-1].first) + abs(h.second - chiken[i-1].second));
                }
            }
            ret += dis; 
        }
        ans = min(ans, ret);
    }
    cout << ans;
}