[백준] 16945번 : 매직 스퀘어로 변경하기 (C++)

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

---

문제)

1부터 N2까지의 수가 하나씩 채워져 있는 크기가 N×N인 배열이 있고, 이 배열의 모든 행, 열, 길이가 N인 대각선의 합이 모두 같을 때, 매직 스퀘어라고 한다.

크기가 3×3인 배열 A가 주어졌을 때, 이 배열을 매직 스퀘어로 변경하려고 한다. 한 칸에 있는 수 a를 b로 변경하는 비용은 |a - b| 이다. 예를 들어, 아래와 같은 경우를 살펴보자.

5 3 4
1 5 8
6 4 2

이 배열의 수를 아래와 같이 변경하면 매직 스퀘어가 되고, 비용은 |5 - 8| + |8 - 9| + |4 - 7| = 7 이다.

8 3 4
1 5 9
6 7 2

3×3 크기의 배열 A가 주어졌을 때, 이 배열을 매직 스퀘어로 변경하는 비용의 최솟값을 구해보자. 배열 A는 1부터 9까지의 수로만 채워져 있고, 매직 스퀘어로 변경한 배열도 1부터 9까지의 수로만 채워져 있어야 한다.

 

 

입력 :

총 세 개의 줄에 걸쳐서 배열 A의 원소가 주어진다.

 

 

 

 

출력 :

첫째 줄에 배열 A를 매직 스퀘어로 변경하는 비용의 최솟값을 출력한다.

 

 

 

 

 

 

 

풀이)

// 16945. 매직 스퀘어로 변경하기
#include <iostream>
#include <vector>
#include <limits.h>
 
using namespace std;
 
int n;
vector<vector<int>> vec(3, vector<int>(3));
vector<vector<int>> arr(3, vector<int>(3));
vector<bool> visited(10, false);
 
int ans = INT_MAX;
 
// 매직 스퀘어 확인
bool check()
{
    for (int i = 0; i < 3; i++)
    {
        int total = 0;
        for (int j = 0; j < 3; j++)
        {
            total += arr[i][j];
        }
 
        if (total != 15) return false;
    }
 
    for (int i = 0; i < 3; i++)
    {
        int total = 0;
        for (int j = 0; j < 3; j++)
        {
            total += arr[j][i];
        }
 
        if (total != 15) return false;
    }
 
    if (arr[0][0] + arr[1][1] + arr[2][2] != 15) return false;
    if (arr[0][2] + arr[1][1] + arr[2][0] != 15) return false;
 
    return true;
}
 
// cur이 2차원이므로 x, y로 대체된다.
void recur(int x, int y, int price)
{
    // 만약 y가 행의 끝에 도달했다면 
    if (y == 3)
    {
        x++;
        y = 0;
    }
 
    if (x == 3)
    {
        // 매직 스퀘어 확인
        if (!check()) return;
        ans = min(ans, price);
        return;
    }
 
    for (int i = 1; i < 10; i++)
    {
        // 중복수 제거 -> 해당 수를 사용했는지
        if (visited[i] == true) continue;
 
        visited[i] = true;
        arr[x][y] = i;
        recur(x, y + 1, price + abs(vec[x][y] - i));
        visited[i] = false;
    }
}
 
int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(0);
 
    // 입력 받기
    for (auto& ele : vec) for (int& e : ele) cin >> e;
 
    recur(0, 0, 0);
 
    cout << ans;
 
    return 0;
}
 
 

---

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

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