퍼즐 조각 채우기 C++

https://programmers.co.kr/learn/courses/30/lessons/84021

코딩테스트 연습 - 퍼즐 조각 채우기

#include <string>
#include <vector>
#include <cstring>
#include <queue>
#include <algorithm>
#include <iostream>

using namespace std;
vector < vector<pair<int, int>>> t;
int visited[55][55];
struct MOVE { int x, y; };
MOVE mv[4] = { { 1,0 },{ -1,0 },{ 0,1 },{ 0,-1 } };

void bfs(int mi, int mj, vector<vector<int>> map) {
	vector<pair<int, int>> tmp;

	queue<pair<int, int>> q;
	q.push({ mi,mj });

	while (!q.empty()) {
		int i = q.front().first;
		int j = q.front().second;
		q.pop();

		tmp.push_back({ i,j });
		for (int k = 0; k < 4; k++) {
			int movei = i + mv[k].x;
			int movej = j + mv[k].y;

			if (!(movei >= 0 && movei < map.size() && movej >= 0 && movej < map.size())) continue;
			if (visited[movei][movej] == 1) continue;

			if (map[movei][movej] == 1) {
				visited[movei][movej] = 1;
				q.push({ movei,movej });
			}
		}
	}

	t.push_back(tmp);
}

bool same(vector<vector<int>>& map, vector<pair<int, int>> bl ) {
	int n = map.size();
	for (int i = -n + 1; i < n; i++) {
		for (int j = -n + 1; j < n; j++) {
			vector<pair<int, int>> tmp;
			for (auto v : bl) tmp.push_back({ v.first + i,v.second + j });

			int count = 0;
			for (int k = 0; k < tmp.size(); k++) {
				if (!(tmp[k].first >= 0 && tmp[k].first < n && tmp[k].second >= 0 && tmp[k].second < n)) continue;
				if (map[tmp[k].first][tmp[k].second] == 0) count++;
				else break;
			}
			bool flag = true;
			if (count == tmp.size()) {
				for (int k = 0; k < tmp.size(); k++) {
					map[tmp[k].first][tmp[k].second] = 1;
				}
				for (int ii = 0; ii < tmp.size(); ii++) {
					for (int k = 0; k < 4; k++) {
						int movei = tmp[ii].first + mv[k].x;
						int movej = tmp[ii].second + mv[k].y;

						if (!(movei >= 0 && movei < n && movej >= 0 && movej < n)) continue;
						if (map[movei][movej] == 0) {
							if (find(tmp.begin(), tmp.end(), make_pair(movei, movej)) == tmp.end()) {
								flag = false;
								break;
							}
						}
					}
					if (flag == false) break;
				}
				if (flag == true) {
					return true;
				}
				else {
					for (int k = 0; k < tmp.size(); k++) {
						map[tmp[k].first][tmp[k].second] = 0;
					}
				}
			}
		}
	}
	return false;
}

int solution(vector<vector<int>> game_board, vector<vector<int>> table) {
	int answer = 0;

	memset(visited, -1, sizeof(visited));
	for (int i = 0; i < table.size(); i++) {
		for (int j = 0; j < table[i].size(); j++) {
			if (table[i][j] == 1 && visited[i][j] == -1) {
				visited[i][j] = 1;
				bfs(i, j, table);
			}
		}
	}

	vector<bool> use(t.size(), false);
	vector<vector<int>> tmp(game_board.size(), vector<int>(game_board.size(), 0));
	for (int k = 0; k < 4; k++) {
		//rotate
		for (int i = 0; i < game_board.size(); i++) {
			for (int j = 0; j < game_board.size(); j++) {
				tmp[j][game_board.size()-i-1] = game_board[i][j];
			}
		}

		for (int i = 0; i < t.size(); i++) {
			if (use[i] == false && same(tmp, t[i]) == true) {
				answer += t[i].size();
				use[i] = true;
			}
		}

		for (int i = 0; i < game_board.size(); i++) {
			for (int j = 0; j < game_board.size(); j++) {
				game_board[i][j] = tmp[i][j];
			}
		}
	}
	return answer;
}