[해커랭크] Forming a Magic Square (C++)

문제 링크: www.hackerrank.com/challenges/magic-square-forming/problem

Forming a Magic Square | HackerRank

1. 주의할 점

- 매직 스퀘어를 이루는 경우가 몇개 없어서 전부 작성하고 풀 수 있지만, DFS로 풀 경우 가로 세로 대각선의 합이 항상 15가 되야 한다

- 중앙의 값은 무조건 5여야 한다

 

2. 구현

- 입력받은 S벡터의 중앙값이 5가 아니라면, 5로 바꾼 이후 차이만큼 Cnt값을 추가하며 DFS()를 시작한다

- 중앙이 5이므로, 중앙을 기준으로 정의될 수 있는 양끝값을 Check[][] 배열에 담는다

- XY[] 배열에는 (0,0) 부터 시작해서 시계방향으로 돌때, 행*3+열의 값을 저장한다

- DFS() 함수에서 중앙을 기준으로 4쌍만 맞추면(Idx==4) 가로 세로의 합이 15인지 확인하고, 15라면 최소값과 비교한다

- 4쌍이 맞춰지지 않은 경우(Idx!=4) For문을 통해 모든 쌍을 겹치지 않게 대입해보며 Idx=4가 될때까지 구한다

 

[핵심 함수만 표시]

int cnt[10];
int ans = 36;
int check[4][2] = { {1,9},{2,8},{3,7},{4,6} };
int xy[8] = { 0,1,2,5,8,7,6,3 };
bool flag[4] = { false, };
// Complete the formingMagicSquare function below.

void dfs(vector<vector<int>> s, int idx, int cnt) {
	if (idx == 4) {
		bool avail = true;
		for (int i = 0; i < 3; i++) {
			if (s[0][i] + s[1][i] + s[2][i] != 15) {
				avail = false;
				break;
			}
			if (s[i][0] + s[i][1] + s[i][2] != 15) {
				avail = false;
				break;
			}
		}
		if (avail) 
			ans = min(ans, cnt);		
		return;
	}

	for (int i = 0; i < 4; i++) {
		if (flag[i]) continue;
		//중앙기준으로 대칭점
		int a = s[xy[idx] / 3][xy[idx] % 3];
		int b = s[xy[idx + 4] / 3][xy[idx + 4] % 3];
		
		flag[i] = true;
		int temp = abs(a - check[i][0]) + abs(b - check[i][1]);
		s[xy[idx] / 3][xy[idx] % 3] = check[i][0];
		s[xy[idx + 4] / 3][xy[idx + 4] % 3] = check[i][1];
		dfs(s, idx + 1, cnt + temp);

		s[xy[idx] / 3][xy[idx] % 3] = check[i][1];
		s[xy[idx + 4] / 3][xy[idx + 4] % 3] = check[i][0];
		temp = abs(a - check[i][1]) + abs(b - check[i][0]);
		dfs(s, idx + 1, cnt + temp);

		s[xy[idx] / 3][xy[idx] % 3] = a;
		s[xy[idx + 4] / 3][xy[idx + 4] % 3] = b;
		flag[i] = false;
	}
}

int formingMagicSquare(vector<vector<int>> s) {	
	int vv = s[1][1];
	if (vv != 5) 
		s[1][1] = 5;	
	dfs(s, 0, abs(vv - 5)); //중앙은 무조건 0
	return ans;
}