[3] 매직 스퀘어(magic square)

매직 스퀘어는 n×n 행렬에서 행과 열, 대각선의 합이 모두 같은 행렬을 의미합니다.

 

5×5 매직 스퀘어

위는 같이 행, 열 대각선의 합이 모두 65로 동일한 매직 스퀘어 입니다.

 

Coexter는 매직 스퀘어를 만드는 방법을 제안했습니다.

우선 첫번째 행의 가운데에 1을 넣고, 왼쪽 대각선 쪽으로 올라가면서 2, 3, ... 을 넣다가

square 바깥으로 나가게 되면 반대편으로 이동하여 계속 왼쪽 대각선쪽으로 올라갑니다.

만약 이미 숫자가 채워져 있다면 바로 밑에 칸부터 다시 시작합니다.

 

이를 C언어로 구현해볼까요?

 

#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>
#include <stdlib.h>
#define MAXSIZE 15
 
int main() {
    int N, row, col;
    int square[MAXSIZE][MAXSIZE];
    int i, j;
 
    printf("Magic square의 크기를 입력하세요: ");
    scanf("%d", &N);
 
    // 입력받은 크기가 짝수이거나 너무 작거나 큰 경우
    if (N % 2 == 0 || N < 1 || N >= MAXSIZE) {
        fprintf(stderr, "size error");
        exit(1);
    }
 
    // square 초기화
    for (i = 0; i < N; i++) {
        for (j = 0; j < N; j++) {
            square[i][j] = 0;
        }
    }
 
    // 1행의 가운데에 1 넣기
    square[0][(N - 1) / 2] = 1;
    
    // i 는 현재 행, j는 현재 열을 의미
    i = 0;
    j = (N - 1) / 2;
 
    // 숫자 넣기
    for (int n = 2; n <= N * N; n++) {
        // row, col은 왼쪽 위로 이동한 행과 열을 의미
        // 위로 이동해야 하므로 row는 하나 작게
        // 왼쪽으로 이동해야 하므로 col또한 하나 작게 한다.
        // 이 때 square 바깥으로 넘어가면 반대편으로 보낸다.
        row = (i - 1 < 0) ? (N - 1) : (i - 1);
        col = (j - 1 < 0) ? (N - 1) : (j - 1);
 
        // 해당 자리에 이미 숫자가 있는 경우
        if (square[row][col]) {
            i = (++i) % N;
        }
        // 해당 자리에 숫자가 없는 경우
        else {
            i = row;
            j = col;
        }
        square[i][j] = n;
    }
 
    // magic square 출력
    for (i = 0; i < N; i++) {
        for (j = 0; j < N; j++) {
            printf("%4d", square[i][j]);
        }
        printf("\n");
    }
 
    return 0;
}