HankerRank Forming a Magic Square(Medium) 문제풀이

문제

We define a magic square to be an n*n matrix of distinct positive integers from 1 to n^2 where the sum of any row, column, or diagonal of length n is always equal to the same number: the magic constant.

You will be given a 3*3 matrix s of integers in the inclusive range [1, 9]. We can convert any digit a to any other digit b in the range [1, 9] at cost of |a-b|. Given s, convert it into a magic square at minimal cost. Print this cost on a new line.

Note: The resulting magic square must contain distinct integers in the inclusive range [1,9]

Example
$s = [[5, 3, 4], [1, 5, 8], [6, 4, 2]]
The matrix looks like this:

We can convert it to the following magic square:
8 3 4
1 5 9
6 7 2

This took three replacements at a cost of |5-8|+|8-9|+|4-7|=7

Function Description
Complete the formingMagicSquare function in the editor below.
formingMagicSquare has the following parameter(s):
int s[3][3]: a 3*3 array of integers

Returns
int: the minimal total cost of converting the input square to a magic square

Input Format
Each of the 3 lines contains three space-separated integers of row s[i].

Explanation 0
If we change the bottom right value, s[2][2], from 5 to 6 at a cost of [6-5]=1, s becomes a magic square at the minimum possible cost.

 

Explanation 1
Using 0-based indexing, if we make
- s[0][1] -> 9 at a cost of  |9-8| = 1
- s[1][0] -> 3 at a cost of |3-4| = 1
- s[2][0] -> 8 at a cost of |8-6| = 2
then the total cost will be 1 + 1 + 2 = 4.

 

해설

 Magic Square, 즉 마방진 문제다. 모든 행, 열, 대각선은 각자 더한 값이 전부 일치해야만 한다. 문제에서 요구하는 마방진의 크기는 3x3으로 고정이며, 입력된 배열에 있는 숫자를 변환할 때 필요한 최소비용을 구하는 문제다.

 먼저 3x3 배열에서 마방진이 어떻게 만들어질 수 있는지 알아야 한다. 3x3 크기에서는 마방진의 종류가 한 가지 뿐이며, 회전하거나 뒤집는 등의 변환을 통해서 나타날 수 있는 마방진은 8개다. 마방진은 이미 확립된 수학적 구조를 가지고 있기 때문에 배열이 마방진인지 확인하는 가장 효율적인 방법은 미리 정의된 마방진을 참고하는 것이다.

vector<vector<vector<int>>> magic_squares = {
        {{8, 1, 6}, {3, 5, 7}, {4, 9, 2}},
        {{6, 1, 8}, {7, 5, 3}, {2, 9, 4}},
        {{4, 9, 2}, {3, 5, 7}, {8, 1, 6}},
        {{2, 9, 4}, {7, 5, 3}, {6, 1, 8}},
        {{8, 3, 4}, {1, 5, 9}, {6, 7, 2}},
        {{4, 3, 8}, {9, 5, 1}, {2, 7, 6}},
        {{6, 7, 2}, {1, 5, 9}, {8, 3, 4}},
        {{2, 7, 6}, {9, 5, 1}, {4, 3, 8}}
    };

마방진의 형태를 알았으니 브루트포스(=완전탐색) 알고리즘으로 풀면 된다. 모든 경우의 최소 비용을 구해 반환한다면 문제를 풀 수 있다.

정답코드

#include <bits/stdc++.h>

using namespace std;

string ltrim(const string &);
string rtrim(const string &);
vector<string> split(const string &);

/*
 * Complete the 'formingMagicSquare' function below.
 *
 * The function is expected to return an INTEGER.
 * The function accepts 2D_INTEGER_ARRAY s as parameter.
 */

int formingMagicSquare(vector<vector<int>> s) 
{
    vector<vector<vector<int>>> magic_squares = {
        {{8, 1, 6}, {3, 5, 7}, {4, 9, 2}},
        {{6, 1, 8}, {7, 5, 3}, {2, 9, 4}},
        {{4, 9, 2}, {3, 5, 7}, {8, 1, 6}},
        {{2, 9, 4}, {7, 5, 3}, {6, 1, 8}},
        {{8, 3, 4}, {1, 5, 9}, {6, 7, 2}},
        {{4, 3, 8}, {9, 5, 1}, {2, 7, 6}},
        {{6, 7, 2}, {1, 5, 9}, {8, 3, 4}},
        {{2, 7, 6}, {9, 5, 1}, {4, 3, 8}}
    };
    
    int min_cost = INT_MAX;
    
    for (const auto& magic : magic_squares) {
        int cost = 0;
        for (int i = 0; i < 3; ++i) {
            for (int j = 0; j < 3; ++j) {
                cost += abs(s[i][j] - magic[i][j]);
            }
        }
        min_cost = min(min_cost, cost);
    }
    
    return min_cost;
}

int main()
{
    ofstream fout(getenv("OUTPUT_PATH"));

    vector<vector<int>> s(3);

    for (int i = 0; i < 3; i++) {
        s[i].resize(3);

        string s_row_temp_temp;
        getline(cin, s_row_temp_temp);

        vector<string> s_row_temp = split(rtrim(s_row_temp_temp));

        for (int j = 0; j < 3; j++) {
            int s_row_item = stoi(s_row_temp[j]);

            s[i][j] = s_row_item;
        }
    }

    int result = formingMagicSquare(s);

    fout << result << "\n";

    fout.close();

    return 0;
}

string ltrim(const string &str) {
    string s(str);

    s.erase(
        s.begin(),
        find_if(s.begin(), s.end(), not1(ptr_fun<int, int>(isspace)))
    );

    return s;
}

string rtrim(const string &str) {
    string s(str);

    s.erase(
        find_if(s.rbegin(), s.rend(), not1(ptr_fun<int, int>(isspace))).base(),
        s.end()
    );

    return s;
}

vector<string> split(const string &str) {
    vector<string> tokens;

    string::size_type start = 0;
    string::size_type end = 0;

    while ((end = str.find(" ", start)) != string::npos) {
        tokens.push_back(str.substr(start, end - start));

        start = end + 1;
    }

    tokens.push_back(str.substr(start));

    return tokens;
}