[백준] 16945 매직스퀘어로 변경하기 (순열을 이용한 풀이)

처음 접근

인접한 숫자를 좌우상하로 바꾸고 바꾼 행렬에 대해서 매직 스퀘어인지 아닌지 체크를 하려고 했다. 하지만 매직퀘어의 경우로 숫자를 바꿔주기 위해선 최소의 숫자를 최소의 경로를 바꿔야하는데 이러한 경우의 수를 체크하기가 무척 번거로운 접근이 되었다.

 

다른 접근 (풀이)

3행3열의 2차원 배열로 접근하는 것이 아닌, 1차원 벡터로 입력을 받고 매직 스퀘어의 성질을 이용한다. 매직스퀘어는 모든 원소가 중복이 없는 경우이다. 그리고 별도의 매직스퀘어 함수를 만들어서 (1차원 이지만 2차원적 위치로 생각) 입력받은 스퀘어 값과 비교하고 최소 움직임 값(문제에서 말한 숫자를 바꾼 차이 값)을 모두 더해서 최솟값을 구하면 된다.

 

즉 {1,2,3...9} 모든 순열을 돌리면서 매직스퀘어인지 아닌지를 구별하고, 매직스퀘어인 경우라면 입력받은 스퀘어값과 차이를 구해서 이 차이값이 최소가 되는 경우를 출력해주면 된다.

 

include <iostream>
#include <algorithm>
#include <vector>
#include <limits.h>
using namespace std;


bool majicnumcheck(vector<int> p)
{
	//행열이 모두 같은지 체크 매직스퀘어인지 아닌지 확인
	int sum = p[0] + p[1] + p[2];
	if (sum != (p[3] + p[4] + p[5])) return false;
	if (sum != (p[6] + p[7] + p[8])) return false;

	
	if (sum != (p[0] + p[3] + p[6])) return false;
	if (sum != (p[1] + p[4] + p[7])) return false;
	if (sum != (p[2] + p[5] + p[8])) return false;

	if (sum != (p[0] + p[4] + p[8])) return false;
	if (sum != (p[2] + p[4] + p[6])) return false;
	return true;
}

int main()
{
    vector<int> majic{1,2,3,4,5,6,7,8,9};
    vector<int> m(9);

    int answer = INT_MAX;

    for(int i=0;i<9;i++)cin>>m[i];

    do
    {
        if(majicnumcheck(majic)) {
            int im=0;
            for(int i=0;i<9;i++) {
                    im += abs(m[i]-majic[i]);
            }
            answer = min(answer,im); // 입력받은 값에서 매직스퀘어가 되기위한 최솟값을 순열이 끝날때 까지 계속 저장
        }
    } while (next_permutation(majic.begin(),majic.end()));
    
    cout<<answer;
    
    return 0;
}