매직 스퀘어(마방진) 완벽 가이드: 개념, 생성 규칙부터 C++ 구현까지

매직 스퀘어(마방진)란?

매직 스퀘어(마방진)는 차수(order)가 홀수인 정사각형 행렬로, 각 행의 원소 합, 각 열의 원소 합, 그리고 양쪽 대각선의 원소 합이 모두 동일한 값을 갖는 특수한 배열입니다.

각 행, 열, 대각선의 합은 다음 공식으로 간단히 구할 수 있습니다.

n(n² + 1) / 2

마방진 생성 규칙

• 행렬의 첫 번째 행 가운데 열에서 시작하며, 다음 숫자를 배치할 때는 항상 왼쪽 위(대각선 방향)로 이동합니다.
• 행이 범위를 벗어난 경우: 열을 한 칸 왼쪽으로 이동하고, 숫자를 행렬의 마지막 행에 배치한 뒤 다시 왼쪽 위 방향으로 이동을 시도합니다.
• 열이 범위를 벗어난 경우: 행을 한 칸 위로 이동하고, 숫자를 행렬의 마지막 열에 배치한 뒤 다시 왼쪽 위 방향으로 이동을 시도합니다.
• 왼쪽 위 칸이 이미 채워져 있거나 행과 열이 모두 범위를 벗어난 경우: 직전에 배치한 숫자의 바로 아래 칸에 숫자를 배치합니다.

입력 및 출력 예시

입력:
행렬의 차수 5

출력:
15  8  1 24 17
16 14  7  5 23
22 20 13  6  4
 3 21 19 12 10
 9  2 25 18 11

알고리즘

마방진 생성 함수는 다음과 같이 정의합니다.

createSquare(mat, r, c)

입력: 행렬 mat과 행·열의 크기 r, c

출력: 완성된 마방진 행렬

시작
    count := 1
    mat의 모든 원소를 0으로 초기화
    range := r * c
    i := 0
    j := c / 2
    mat[i, j] := count              // 첫 번째 행의 중앙 위치

    while count < range 동안 반복:
        count를 1 증가
        if i와 j가 모두 행렬 범위를 벗어나면:
            i를 1 증가
        else if i만 범위를 벗어나면:
            i := r - 1
            j를 1 감소
        else if j만 범위를 벗어나면:
            j := c - 1
            i를 1 감소
        else if (i, j)가 행렬 안에 있고 mat[i, j] ≠ 0이면:
            i를 1 증가
        else:
            i와 j를 각각 1 감소
        mat[i, j] := count
    행렬 mat 출력
끝

C++ 구현 예제

#include<iostream>
#include<iomanip>
using namespace std;

void createSquare(int **array, int r, int c) {
    int i, j, count = 1, range;
    for(i = 0; i<r; i++)
        for(j = 0; j<c; j++)
            array[i][j] = 0;         // 모든 원소를 0으로 초기화

    range = r * c;
    i = 0;
    j = c / 2;
    array[i][j] = count;

    while(count < range) {
        count++;
        if((i-1) < 0 && (j-1) < 0)          // 행과 열이 모두 범위를 벗어난 경우
            i++;
        else if((i-1) < 0) {                // 행만 벗어난 경우: 마지막 행으로 이동 후 j 감소
            i = r - 1;
            j--;
        } else if((j-1) < 0) {              // 열만 벗어난 경우: 마지막 열로 이동 후 i 감소
            j = c - 1;
            i--;
        } else if(array[i-1][j-1] != 0)     // 대각선 칸이 이미 채워져 있으면 아래 행으로 이동
            i++;
        else {
            i--;
            j--;
        }
        array[i][j] = count;
    }

    // 완성된 마방진 출력
    for(i = 0; i<r; i++) {
        for(j = 0; j<c; j++)
            cout << setw(3) << array[i][j];
        cout << endl;
    }
}

main() {
    int** matrix;
    int row, col;
    cout << "정방 행렬의 차수(홀수)를 입력하세요 : ";
    cin >> row;
    col = row;

    matrix = new int*[row];

    for(int i = 0; i<row; i++) {
        matrix[i] = new int[col];
    }
    createSquare(matrix, row, col);
}

실행 결과

정방 행렬의 차수(홀수)를 입력하세요 : 5
 15  8  1 24 17
 16 14  7  5 23
 22 20 13  6  4
  3 21 19 12 10
  9  2 25 18 11

차수가 5일 때 각 행, 열, 대각선의 합은 공식에 따라 5 × (25 + 1) / 2 = 65로 모두 일치하는 것을 확인할 수 있습니다.