백준 16945번 매직 스퀘어로 변경하기 C++

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

 

데이터의 크기가 크지 않기 때문에 백트래킹을 이용하여 모든 경우를 조사해서 매직 스퀘어가 되는 몇 가지 경우를 추출할 수 있다. 

 

처음 입력받은 데이터와 추출한 매직 스퀘어들을 비교해서 바꾸는데 가장 적은 값이 필요한 경우를 찾았다.

 

그리고 3*3배열이라서 1차원 배열로 관리하는게 더 편할 것 같아서 1차원 배열로 바꿔서 문제를 해결하였다.

 

#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>

using namespace std;
typedef long long ll;

vector<int> origin(10);
vector<bool> visited(10, false);
vector<int> nums;
int ans = 10000;

bool isMagicSquare() {
	bool ret = true;

	// 1 2 3
	// 4 5 6
	// 7 8 9

	int sum = nums[1] + nums[2] + nums[3];

	//가로
	if (sum != nums[4] + nums[5] + nums[6]) ret = false;
	if (sum != nums[7] + nums[8] + nums[9]) ret = false;
	//세로
	if (sum != nums[1] + nums[4] + nums[7]) ret = false;
	if (sum != nums[2] + nums[5] + nums[8]) ret = false;
	if (sum != nums[3] + nums[6] + nums[9]) ret = false;
	//대각선
	if (sum != nums[1] + nums[5] + nums[9]) ret = false;
	if (sum != nums[3] + nums[5] + nums[7]) ret = false;

	return ret;
}

void BT(int cnt) {
	if (cnt > 8) {
		if (isMagicSquare()) {
			int sum = 0;
			for (int i = 1; i <= 9; i++) {
				sum += abs(origin[i] - nums[i]);
			}
			ans = min(ans, sum);
		}
		return;
	}
	for (int i = 1; i <= 9; i++) {
		if (visited[i]) continue;
		nums.push_back(i);
		visited[i] = true;
		BT(cnt + 1);
		nums.pop_back();
		visited[i] = false;
	}
}

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

	for (int i = 1; i <= 9; i++) {
		cin >> origin[i];
	}
	nums.push_back(0);
	BT(0);
	cout << ans;
};