[ boj : 20208 ] 진우의 민트초코우유

www.acmicpc.net/problem/20208

20208번: 진우의 민트초코우유

문제 : 민트초코가 최대 10개 주어지고 무조건 다시 집으로 돌아와야 할때 최대로 먹을 수 있는 민트초코의 개수를 구하시오. 각 거리마다 피가 1씩 줄어든다.

 

해설 : 처음에 비트마스킹을 이용해서 풀어보려고 했는데 어디서 꼬였는지 잘안되네요....

그래서 그냥 브루트 포스로 풀었습니다.

먼저 집+모든민트초코 의 위치에서 각각으로 갈 수 있는 거리를 전부 싹다 구해줍시다.

그리고 난 후 1~x(민트초코의 개수) 를 permutation을 통해 순서를 미리 정해준 후 이 순서대로 갈 수 있을때까지 쭉쭉 가줍니다. 최대값의 개수 또한 중간에 계속 갱신을 해주고 만약 갈 수 없다면 break로 한루틴을 끝내주면 되겠습니다.

 

(비트마스킹으로 풀면 그 해설도 올릴게요 ㅠ)

#include<bits/stdc++.h>

using namespace std;

struct info {
	int x, y, number;
};

int n, m, h,ans=0;
int board[10][10];
int dist[12][12];
int visit[11],per[11];
vector<info> v;

void permutation(int depth);

int main()
{
	ios::sync_with_stdio(false);
	cin.tie(0);

	int num = 1;
	cin >> n >> m >> h;
	for (int i = 0; i < n; i++)
		for (int j = 0; j < n; j++) {
			cin >> board[i][j];
			if (board[i][j] == 2) {
				v.push_back({ i,j,num });
				num++;
			}
			if (board[i][j] == 1)
				v.push_back({ i,j,0 });
		}
	
	for (int i = 0; i < v.size(); i++)
		for (int j = 0; j < i; j++)
			dist[v[i].number][v[j].number] = dist[v[j].number][v[i].number] = abs(v[i].x - v[j].x) + abs(v[i].y - v[j].y);
	permutation(0);
	cout << ans;
	return 0;
}
void permutation(int depth)
{
	if (depth == v.size()-1) {
		int s = 0, cnt = 0, cost = m;
		for (int i = 1; i < v.size(); i++) {
			if (cost - dist[s][per[i]] >= 0)cnt++;
			else break;
			cost = cost - dist[s][per[i]] + h;
			s = per[i];
			if (cost - dist[0][s] >= 0)
				ans = max(ans, cnt);
		}
		
		return;
	}
	for (int i = 1; i < v.size(); i++) {
		if (!visit[i]) {
			per[depth+1] = i;
			visit[i] = 1;
			permutation(depth + 1);
			visit[i] = 0;
		}
	}
}