백준 10472: 십자뒤집기

문제 요약

당신에게 3x3 크기의 보드가 주어진다. 각각의 칸은 처음에 흰색 혹은 검은색이다. 만약 당신이 어떤 칸을 클릭한다면 당신이 클릭한 칸과 그 칸에 인접한 동서남북 네 칸이 (존재한다면) 검은색에서 흰색으로, 혹은 흰색에서 검은색으로 변할 것이다.

당신은 모든 칸이 흰색인 3x3 보드를 입력으로 주어지는 보드의 형태로 바꾸려고 한다. 보드를 회전시킬수는 없다.

흰 보드를 입력에 주어진 보드로 바꾸는 데 필요한 최소 클릭의 횟수를 구하여라

문제 분류

• 그래프 이론
• 브루트포스 알고리즘
• 그래프 탐색
• BFS
• 비트 마스킹

문제 풀이

최소 탐색 횟수이므로 BFS로 탐색하면 된다. 해결하는 데에는 두가지 방법이 있는데, string을 사용하는 방식과 int와 비트 마스킹을 사용하는 방식이다.

첫번째 방식은 string으로 탐색하면서, 방문 여부는 set으로 파악하였다.

왼상단부터 우하단까지를 각 기준으로 잡고, 상하좌우 및 기준까지 문자를 반전시킨 뒤, 새롭게 나온 문자열로 큐에 삽입함으로써 BFS를 했다.

풀이 코드

1. string과 set으로 푼 예시

#include <stdio.h>
#include <iostream>
#include <algorithm>
#include <queue>
#include <set>

using namespace std;

int dir[5][2] = { {0,1},{0,-1},{0,0},{1,0},{-1,0} };

int main() {
	int t, qsize, level;
	string str[3],val, cop;
	queue<string> q;
	set<string> s;
	cin >> t;
	while(t--) {
		bool sol = false;
		level = -1;
		for (int i = 0; i < 3; i++)
			cin >> str[i];
		s.clear();
		q = queue<string>();
		cop = str[0] + str[1] + str[2];
		q.push(cop);
		s.insert(cop);
		while (!q.empty()) {
			level++;
			qsize = q.size();
			while (qsize--) {
				val = q.front();
				q.pop();
				if (val == ".........") {
					sol = true;
					break;
				}
				for (int i = 0; i < 9; i++) {
					int x = i % 3, y = i / 3;
					cop = val;
					for (int j = 0; j < 5; j++) {
						int nx = x + dir[j][0];
						int ny = y + dir[j][1];
						if (nx >= 0 && nx < 3 && ny >= 0 && ny < 3) {
							if (cop[ny * 3 + nx] == '.') cop[ny * 3 + nx] = '*';
							else cop[ny * 3 + nx] = '.';
						}
					}
					if (!s.count(cop)) {
						s.insert(cop);
						q.push(cop);
					}
				}
			}
			if (sol) break;
		}
		printf("%d\n", level);
	}
	return 0;
}

2. int, visited[]로 푼 예시

#include <stdio.h>
#include <iostream>
#include <algorithm>
#include <queue>

using namespace std;

int dir[5][2] = { {0,1},{0,-1},{0,0},{1,0},{-1,0} };
bool visited[1 << 9];

int main() {
	int t, qsize, level, val, cop;
	string str[3];
	queue<int> q;
	cin >> t;
	while (t--) {
		bool sol = false;
		val = 0;
		level = -1;
		for (int i = 0; i < 3; i++) {
			cin >> str[i];
			for (int j = 0; j < 3; j++) {
				if (str[i][j] == '*') val |= (1 << i * 3 + j);
			}
		}
		memset(visited, false, sizeof(visited));
		q = queue<int>();
		q.push(val);
		visited[val] = true;
		while (!q.empty()) {
			level++;
			qsize = q.size();
			while (qsize--) {
				val = q.front();
				q.pop();
				if (!val) {
					sol = true;
					break;
				}
				for (int i = 0; i < 9; i++) {
					int x = i % 3, y = i / 3;
					cop = val;
					for (int j = 0; j < 5; j++) {
						int nx = x + dir[j][0];
						int ny = y + dir[j][1];
						if (nx >= 0 && nx < 3 && ny >= 0 && ny < 3)
							cop ^= (1 << (ny * 3 + nx));
					}
					if (!visited[cop]) {
						visited[cop] = true;
						q.push(cop);
					}
				}
			}
			if (sol) break;
		}
		printf("%d\n", level);
	}
	return 0;
}