언제나 처음처럼

[문제 링크]

왠지 영어로 된 알고리즘 문제를 풀어봐야 할 것 같아서 풀게되었다.

문제는 간단했다. 한 블록을 뒤집으면 상하좌우에 존재하는 블록들까지 동시에 뒤집어지는데, 모든 블록을 블랙 또는 화이트가 되도록 만들기 위해 뒤집는 최소한의 횟수를 구하는 문제였다.

최소한의 횟수를 구하기 위해 bfs를 구현하면 간단히 풀 수 있는 문제인데, 한가지 문제가 있다면 이전에 등장했던 보드판의 상태를 중복탐색 하는 것을 막기 위해 방문체크를 해줘야 하는데, 블록의 형태를 어떻게 표현할 것인지가 문제였다.

보드판은 항상 4x4 이므로 보드판에 존재하는 블록의 개수 또한 항상 16개라는 것을 알 수 있다.

따라서, 비트마스크 기법을 활용하면 보드판의 상태를 integer 타입의 정수형 데이터로 표현하는 것이 가능하다.

보드판의 좌표 (y,x)를 (4*y)+x 공식에 대입하여 자릿수를 구한 다음, OR 연산을 통해 해당 자릿수의 값을 블랙일 경우 1, 화이트일 경우 0으로 세팅하고, 공을 뒤집는 작업은 XOR 연산을 통해 값을 반전시켜줌으로써 간단하게 보드판을 관리할 수 있다.

#include <iostream>
#include <vector>
#include <string>
#include <queue>
using namespace std;

int dy[4] = { 0,0,1,-1 };
int dx[4] = { 1,-1,0,0 };

int ptod(int y, int x) {
	return (y * 4) + x;
}

int bfs(int start) {
	int allBlack = (1 << 16) - 1;
	int allWhite = 0;
	bool visited[(1 << 16)] = { false };

	queue<pair<int, int>> q;
	q.push({ start,0 });
	visited[start] = true;

	while (!q.empty()) {
		int here = q.front().first;
		int round = q.front().second;
		q.pop();

		if (here == allBlack || here == allWhite)
			return round;

		for(int i=0; i<4; i++)
			for (int j = 0; j < 4; j++) {
				int there = here;
				there ^= (1 << (ptod(i, j)));

				for (int k = 0; k < 4; k++) {
					int nextY = i + dy[k];
					int nextX = j + dx[k];
					if (nextY >= 0 && nextY < 4 && nextX >= 0 && nextX < 4) {
						there ^= (1 << (ptod(nextY, nextX)));
					}
				}
				if (!visited[there]) {
					visited[there] = true;
					q.push({ there, round + 1 });
				}
			}
	}

	return -1;
}

int solution(vector<string>& input) {
	int inputNumber = 0;
	for(int i=0; i<4; i++)
		for (int j = 0; j < 4; j++) {
			int digit = ptod(i, j);
			if (input[i][j] == 'b')
				inputNumber |= (1 << digit);
		}

	return bfs(inputNumber);
}

int main(void) {
	vector<string> input;
	for (int i = 0; i < 4; i++) {
		string s;
		cin >> s;
		input.push_back(s);
	}

	int result = solution(input);
	if (result != -1)
		cout << result;
	else
		cout << "Impossible";

	return 0;
}

[문제 링크]

https://onlytrying.tistory.com/34?category=808917

4달전 완전탐색을 공부할 때 한번 푼적이 있는 문제였다.

알파벳이 a~z 까지 총 26개 존재하기 때문에 32bit인 int형의 2진수로 a~z 까지 알파벳을 배웠는지 안배웠는지 여부를 표현할 수 있다.

따라서 비트마스크를 사용할 수 있다는 것을 알 수 있으며, 이를 사용하여 더 효율적인 알고리즘으로 재구현하였다.

핵심은 입력받은 단어에 포함된 알파벳을 OR 연산을 통해 int형 변수 word 에 저장함으로써

배운 알파벳의 정보를 가지고 있는 learn과 AND 연산하여 가능 불가능 여부를 O(1) 에 확인할 수 있다는 것이다.

#include <iostream>
#include <string>
using namespace std;

int learn, word[50];

int max(int a, int b) { return a > b ? a : b; }

int DFS(int start, int N, int K, int learning)
{
	int ret = 0;

	if (learning == K)
	{
		for (int i = 0; i < N; i++)
			if ((word[i] & learn) == word[i]) 
				ret++;

		return ret;
	}

	for (int i = start; i < 26; i++)
	{
		if ((learn & (1 << i)) == 0)
		{
			learn |= (1 << i);
			ret = max(ret, DFS(i + 1, N, K, learning + 1));
			learn &= ~(1 << i);
		}
	}

	return ret;
}

int main(void)
{
	learn |= 1 << ('a' - 'a');
	learn |= 1 << ('c' - 'a');
	learn |= 1 << ('i' - 'a');
	learn |= 1 << ('n' - 'a');
	learn |= 1 << ('t' - 'a');

	int N, K;
	cin >> N >> K;

	for (int i = 0; i < N; i++)
	{
		string str;
		cin >> str;

		for (int j = 0; j < str.length(); j++)
			word[i] |= (1 << (str[j] - 'a'));
	}
		
	if (K < 5 || K == 26)
		cout << (K == 26 ? N : 0) << endl;
	else
		cout << DFS(0, N, K, 5) << endl;

	return 0;
}

알고리즘 200일 프로젝트 - 134 day

[문제 링크]

알고리즘 문제해결전략의 비트마스크 부분을 공부하면서 풀게된 첫 문제였다.

주어지는 입력의 범위가 20 미만으로 작기 때문에 최대 32비트 길이의 2진수를 표현할 수 있는 int형 정수의 비트연산을 통해 효율적으로 정답을 구할 수 있다.

#include <iostream>
#include <cstring>
using namespace std;

const int INF = 987654321;
int N, K, M, L;
int preceding[12], classes[10];
int memo[10][1 << 12];

int min(int a, int b) { return a < b ? a : b; }

int BitCount(int taken)
{
	int cnt = 0;

	for (int i = 0; i < N; i++)
		if (taken & (1 << i))
			cnt++;

	return cnt;
}

int Topdown(int semester, int taken)
{
	if (BitCount(taken) >= K) return 0;
	if (semester >= M) return INF;

	int& ret = memo[semester][taken];
	if (ret != 0) return ret;

	ret = INF;

	int canTake = (classes[semester] & ~taken);

	for (int i = 0; i < N; i++)
		if ((canTake & (1 << i)) && (preceding[i] & taken) != preceding[i])
			canTake &= ~(1 << i);

	for (int take = canTake; take > 0; take = ((take - 1) & canTake))
	{
		if(BitCount(take) > L) continue;
		
		ret = min(ret, 1 + Topdown(semester + 1, taken | take));	
	}

	ret = min(ret, Topdown(semester+1, taken));

	return ret;
}

int main(void)
{
	int test_case;
	cin >> test_case;

	while (test_case--)
	{
		memset(preceding, 0, sizeof(preceding));
		memset(classes, 0, sizeof(classes));
		memset(memo, 0, sizeof(memo));

		cin >> N >> K >> M >> L;

		
		for (int i = 0; i < N; i++)
		{
			int R;
			cin >> R;
			
			for (int j = 0; j < R; j++)
			{
				int num;
				cin >> num;
				preceding[i] |= (1 << num);
			}
		}

		for (int i = 0; i < M; i++)
		{
			int C;
			cin >> C;

			for (int j = 0; j < C; j++)
			{
				int num;
				cin >> num;
				
				classes[i] |= (1 << num);
			}
		}

		int result = Topdown(0, 0);

		if (result == INF)
			cout << "IMPOSSIBLE" << endl;
		else
			cout << result << endl;
	}

	return 0;
}

알고리즘 200일 프로젝트 - 134 day