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

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

16945번: 매직 스퀘어로 변경하기

 

 

 

 

 

<접근방법>

n이 매우 작으므로 완전 탐색으로 풀 수 있습니다.

순열로 사각형을 만들어서 가중치를 계산하고 최솟값을 저장해나갑니다.

 

 

 

<느낀 점>

 

 

 

---

 

 

 

<코드>

#include <iostream>
#include <algorithm>
using namespace std;

int a[9], b[9], res = 98765431;
bool visit[10];

int cal() {
	int tres = 0;
	for (int i = 0; i < 9; i++) {
		int tmp = abs(a[i] - b[i]);
		tres += tmp;
	}
	return tres;
}

bool check() {
	int sum = b[0] + b[1] + b[2];

	for (int i = 0; i < 3; i++) {
		int tsum = 0;
		for (int j = 0; j < 3; j++) {
			tsum += b[i * 3 + j];
		}
		if (sum != tsum) return false;
	}

	for (int i = 0; i < 3; i++) {
		int tsum = 0;
		for (int j = 0; j < 9; j += 3) {
			tsum += b[i + j];
		}
		if (sum != tsum) return false;
	}

	int tsum = b[0] + b[4] + b[8];
	if (sum != tsum) return false;

	tsum = b[2] + b[4] + b[6];
	if (sum != tsum) return false;
	return true;
}

void dfs(int dep = 0) {
	if (dep == 9) {
		if (check()) {
			res = min(res, cal());
		}
		return;
	}

	for (int i = 1; i <= 9; i++) {
		if (visit[i]) continue;
		visit[i] = true;
		b[dep] = i;
		dfs(dep + 1);
		visit[i] = false;
	}
}

int main() {
	for (int i = 0; i < 3; i++) {
		for (int j = 0; j < 3; j++) {
			cin >> a[i*3 + j];
		}
	}
	dfs();
	cout << res << '\n';
	return 0;
}