백준 10472번 십자뒤집기 C++

출처 : https://www.acmicpc.net/problem/10472

 

비트마스킹을 활용해서 bfs로 탐색하면서 문제를 해결하였다.

 

#include <iostream>
#include <string>
#include <vector>
#include <math.h>
#include <algorithm>
#include <utility>
#include <stack>
#include <queue>
#include <math.h>
#include <set>
#include <map>
#include <unordered_map>
#include <unordered_set>
#include <iomanip>

using namespace std;
using ll = long long;

int dRow[5] = { 0,-1,0,1,0 };
int dCol[5] = { 0,0,1,0,-1 };

int visited[600] = { false };
int arr[3][3] = { {0,1,2},{3,4,5},{6,7,8} };

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

	int p;
	cin >> p;
	while (p--) {
		int target = 0;
		int cnt = 0;
		string str;
		queue<pair<int ,int>> q;
		for (int i = 0; i < 3; i++) {
			cin >> str;
			for (int j = 0; j < 3; j++) {
				if (str[j] == '*') target += 1 << cnt;
				cnt++;
			}
		}
		q.push({ 0,0 });
		visited[0] = true;
		int ans = -1;
		while (!q.empty()) {
			auto curr = q.front();
			q.pop();
			if (curr.first == target) {
				ans = curr.second;
				break;
			}
			for (int i = 0; i < 3; i++) {
				for (int j = 0; j < 3; j++) {
					int row = i;
					int col = j;
					int nextVal = curr.first;
					for (int k = 0; k < 5; k++) {
						int nextRow = row + dRow[k];
						int nextCol = col + dCol[k];
						if (nextRow < 0 || nextRow >= 3) continue;
						if (nextCol < 0 || nextCol >= 3) continue;
						int nextBlock = 1 << arr[nextRow][nextCol];
						if (curr.first & nextBlock) {
							nextVal = nextVal ^ nextBlock;
						}
						else {
							nextVal = nextVal | nextBlock;
						}
					}
					if (visited[nextVal]) continue;
					visited[nextVal] = true;
					q.push({ nextVal,curr.second + 1 });
				}
			}
		}	
		cout << ans << "\n";
		for (int i = 0; i < 600; i++) {
			visited[i] = false;
		}
	}
};