백준 7425번: Flip Game

[문제 링크]

7425번: Flip Game

---

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

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

 

최소한의 횟수를 구하기 위해 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;
}