[BOJ / 비트마스크 DP] 1102 발전소

www.acmicpc.net/problem/1102

1102번: 발전소

 

1102 발전소

 

알고리즘 : 비트마스크 DP / BFS

비트마스크를 DP배열의 iterator로 사용하는 문제입니다.

dp를 이용해 현재 적용중인 상태에서 이미 들린 상태이거나 이미 결과값을 초과한 경우 가지치기를 하면 됩니다.

문제에서 해결이 안되는 경우에는 -1을 출력하라고 했으나, 모든 발전소는 다른 모든 발전소를 킬 수 있으므로

즉, 키는 비용에 음수값이 주어지는 경우가 없으므로 -1을 출력하는 경우는 모든 발전소가 꺼져있을 때 뿐입니다.

모든 발전소가 꺼져있어도 요구하는 켜진 발전소가 0개이면 0을 출력하여야합니다.

 

 

 

 

< CODE >

#include <iostream>
#include <string>
#include <vector>
#include <queue>
#include <algorithm>
#include <climits>
#include <cstdlib>

using namespace std;

#define MAX 18
#define INTMAX 987654321

struct node
{
	int nBit;
	int pEmp;
	int play = 0;

	node(int b, int p, int z) : nBit(b), pEmp(p), play(z) {}
};

int n;
int fBit;
int cost[MAX][MAX];
queue<node> q;
int dp[1 << 17];

int getCost(int idx, int num)
{
	int i = 0;
	int ret = 0;
	vector<int> mCost(n+1,INTMAX);

	for (int i = 0; i < n; i++)
	{
		for (int j = 0; j < n; j++)
		{
			if (idx & (1 << i))
				mCost[j] = min(mCost[j], cost[i][j]);
		}
	}

	while (i <= n - 1)
	{
		if (num & (1 << i))
			ret += mCost[i];
		i++;
	}

	return ret;
}

int getCount(int num)
{
	int i = 0;
	int ret = 0;

	while (i <= n - 1)
	{
		if (num & (1 << i))
			ret++;
		i++;
	}

	return ret;
}

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

	int limit;
	int result = INTMAX;
	string str;
	
	cin >> n;
	
	for (int i = 0; i < n; i++)
	{
		for (int j = 0; j < n; j++)
		{
			cin >> cost[i][j];
		}
	}

	cin >> str;

	for (int i = 0; i < n; i++)
	{
		if (str[i] == 'Y')
			fBit |= (1 << i);
	}

	for (int i = 0; i <= (1 << 17) - 1; i++)
		dp[i] = INTMAX;

	cin >> limit;
	
	if(limit == 0)
		result = 0;
	
	q.push(node(fBit, getCount(fBit),0));

	while (!q.empty())
	{
		node now = q.front(); q.pop();

		if (dp[now.nBit] < now.play || now.pEmp == 0)
			continue;

		if (now.pEmp >= limit)
		{
			result = min(result, now.play);
			continue;
		}
		
		for(int i = 0; i < n; i++)
		{
			int tBit = (1 << i);
			
			if((tBit & now.nBit) == 0)
			{
				int rBit = now.nBit | tBit;
				int tCost = now.play + getCost(now.nBit, tBit);
				
				if(dp[rBit] > tCost && result > tCost)
				{
					dp[rBit] = tCost;
					q.push(node(rBit, now.pEmp + 1, tCost));
				}
			}
		}
	}

	if (result == INTMAX)
		cout << "-1\n";
	else
		cout << result << '\n';

	return 0;
}

시간 : 100ms

 

태그 : #BOJ발전소 #1102발전소 #BOJ1102 #알고리즘 #백준발전소 #비트마스크 #DP #BFS