C++로 주어진 행렬이 마방진(Magic Square)인지 확인하는 방법

이 글에서는 C++를 사용하여 주어진 행렬이 마방진(Magic Square)인지 판별하는 방법을 알아보겠습니다.

마방진이란?

마방진은 정사각형 행렬의 한 종류로, 각 행의 합, 각 열의 합, 그리고 두 대각선의 합이 모두 동일한 값이 되는 행렬을 말합니다.

예를 들어 다음과 같은 3×3 행렬이 있다고 가정해 보겠습니다.

이 행렬은 마방진입니다. 실제로 각 행의 합(6+1+8, 7+5+3, 2+9+4), 각 열의 합(6+7+2, 1+5+9, 8+3+4), 그리고 두 대각선의 합(6+5+4, 8+5+2)을 계산해 보면 모두 15로 동일하기 때문입니다.

마방진 판별 알고리즘

행렬이 마방진인지 확인하는 절차는 다음과 같습니다.

1. 주대각선(왼쪽 위 → 오른쪽 아래)의 합과 부대각선(오른쪽 위 → 왼쪽 아래)의 합을 구합니다. 두 값이 다르면 마방진이 아닙니다.
2. 각 행의 합을 계산하여 대각선의 합과 비교합니다. 하나라도 다르면 마방진이 아닙니다.
3. 각 열의 합을 계산하여 대각선의 합과 비교합니다. 하나라도 다르면 마방진이 아닙니다.
4. 모든 조건을 통과하면 해당 행렬은 마방진입니다.

C++ 구현 예제

#include <iostream>
#define N 3
using namespace std;

bool isMagicSquare(int mat[][N]) {
    int sum_diag = 0, sum_diag_second = 0;
    // 주대각선의 합 계산
    for (int i = 0; i < N; i++)
        sum_diag = sum_diag + mat[i][i];
    // 부대각선의 합 계산
    for (int i = 0; i < N; i++)
        sum_diag_second = sum_diag_second + mat[i][N-1-i];
    // 두 대각선의 합이 다르면 마방진이 아님
    if (sum_diag != sum_diag_second)
        return false;
    // 각 행의 합 검사
    for (int i = 0; i < N; i++) {
        int rowSum = 0;
        for (int j = 0; j < N; j++)
            rowSum += mat[i][j];
        if (rowSum != sum_diag)
            return false;
    }
    // 각 열의 합 검사
    for (int i = 0; i < N; i++) {
        int colSum = 0;
        for (int j = 0; j < N; j++)
            colSum += mat[j][i];
        if (sum_diag != colSum)
            return false;
    }
    return true;
}

int main() {
    int mat[][N] = {{ 6, 1, 8 },
                    { 7, 5, 3 },
                    { 2, 9, 4 }};
    if (isMagicSquare(mat))
        cout << "It is Magic Square";
    else
        cout << "It is Not a magic Square";
}

실행 결과

It is Magic Square

시간 복잡도

위 알고리즘은 행렬의 모든 원소를 상수 번씩 순회하므로, N×N 행렬 기준 시간 복잡도는 O(N²)이며 공간 복잡도는 O(1)입니다.