[BOJ / 비트마스크 DFS] 17136 색종이 붙이기

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

17136번: 색종이 붙이기

 

17136 색종이 붙이기

 

알고리즘 : 비트마스크 DFS

삼성 A형 기출문제입니다. 문제 풀이 방법은 1767 프로세서 연결하기와 매우 유사합니다.

https://mumomu.tistory.com/13?category=863413

[SWEA / 삼성A형기출] 1767 프로세서 연결하기 풀이

이 문제의 특징을 보면 맵이 한 줄이 10으로 고정되어 있고 0과 1로 이루어진 것을 알 수 있습니다.

이는 하나의 int형으로 한 줄을 관리할 수 있다는 것이고 위의 문제와 유사합니다.

이를 이용하면 시간을 많이 단축할 수 있습니다.

 

그렇게 가능한 칸마다 남아있는 5*5~1*1의 색종이를 붙이고 다음 칸으로 진행하는 것을 반복하면

최저 횟수가 나옵니다. 

 

예전 초등학교 정보올림피아드 지역예선에서 비슷한 문제를 봤던 것 같습니다.

 

 

 

 

< CODE >

#include <iostream>
#include <vector>

using namespace std;

#define MAX 10

vector<pair<int, int>> v;
int result = 987654321;

// 색종이를 붙일 수 있는지 확인
bool bitCheck(int bit, int x, int width)
{
	int chk = (((1 << width) - 1) << x);

	return chk == (chk & bit);
}

// 해당영역의 1을 0으로 바꿔야하므로 해당부분을 1로 만든 뒤 반전하여 &연산
void bitChange(int & bit, int x, int width)
{
	bit &= ~(((1 << width) - 1) << x);
}

void dfs(int cnt, int bit[MAX], int remain[6], int amount)
{
	if (amount == v.size())
	{
		int total = 0;

		for (int i = 1; i < 6; i++)
			total += (5 - remain[i]);

		if (total < result)
			result = total;

		return;
	}
	else if (cnt == v.size())
		return;

	int y = v[cnt].first;
	int x = v[cnt].second;

	if (!bitCheck(bit[y], x, 1))
		dfs(cnt + 1, bit, remain, amount);

	int base[MAX];

    // 비트 복구를 위한 베이스
	for (int i = 0; i < MAX; i++)
		base[i] = bit[i];

	for (int i = 5; i > 0; i--)
	{
		if (remain[i] == 0)
			continue;

		bool chk = true;

		for (int j = 0; j < i; j++)
			chk &= bitCheck(bit[y + j], x, i);

		if (chk)
		{
			for (int j = 0; j < i; j++)
				bitChange(bit[y + j], x, i);

			remain[i] -= 1;

			dfs(cnt + 1, bit, remain, amount + i * i);

			remain[i] += 1;

			for (int j = 0; j < i; j++)
				bit[y + j] = base[y + j];
		}
	}
}

int main()
{
	ios_base::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
	
	int bit[MAX] = { 0, };
	int remain[6] = { 0,5,5,5,5,5 };
	int amount = 0;

	for (int i = 0; i < MAX; i++)
	{
		for (int j = 0; j < MAX; j++)
		{
			int num;

			cin >> num;

			if (num == 1)
			{
				bit[i] |= (1 << j);
				v.push_back({ i,j });
			}
		}
	}

	dfs(0, bit, remain, 0);

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

	return 0;
}

56ms로 통과하였습니다.

 

 

#삼성A형기출 #백준 17136 #17136 색종이붙이기풀이