Computer >> 컴퓨터 >  >> 프로그래밍 >> C++

C++에서 그리드 내 3x3 마방진 개수 세기

개요

주어진 숫자 행렬(그리드) 안에서 3x3 크기의 마방진(Magic Square)이 몇 개 존재하는지 찾는 문제입니다. 마방진은 1부터 9까지의 숫자가 각각 한 번씩만 나타나며, 모든 행, 열, 대각선의 합이 15가 되는 3x3 정사각형을 말합니다.

마방진의 정의와 조건

3x3 마방진이 되기 위한 필수 조건은 다음과 같습니다.

  • 1부터 9까지의 정수가 중복 없이 정확히 한 번씩 등장한다.
  • 모든 숫자의 합은 45이다 (1+2+...+9).
  • 각 행의 합 = 15
  • 각 열의 합 = 15
  • 두 대각선의 합 = 15
  • 중앙에는 반드시 5가 위치한다 (두 대각선의 교차점이므로).

이 중 '중앙이 5'라는 조건은 탐색 시 불필요한 연산을 줄여주는 강력한 필터 역할을 합니다.

입력 및 출력 예시

예시 1: 마방진이 없는 경우

int arr[][] = { { 1, 2, 3, 0 },
                { 4, 5, 6, 1 },
                { 7, 8, 9, 0 } };

출력: Magic Squares present: 0

해설: 왼쪽 상단 3x3 영역은 숫자 1~9가 모두 쓰였지만, 행의 합이 각각 6, 15, 24로 15가 아니므로 마방진이 아닙니다.

1230
4561
7890

예시 2: 마방진이 1개 있는 경우

아래 4x4 그리드에서 왼쪽 상단 3x3 영역이 마방진입니다.

int grid[][] = { { 8, 1, 6, 4 },
                 { 3, 5, 7, 0 },
                 { 4, 9, 2, 1 },
                 { 2, 7, 6, 0 } };

출력: Magic Squares present: 1

8164
3570
4921
2760
  • 행의 합: 8+1+6 = 3+5+7 = 4+9+2 = 15
  • 열의 합: 8+3+4 = 1+5+9 = 6+7+2 = 15
  • 대각선 합: 8+5+2 = 6+5+4 = 15
  • 숫자 1~9가 중복 없이 사용됨

해결 접근법

  1. 그리드 순회: 그리드의 (0,0)부터 (행-2, 열-2)까지 3x3 부분 행렬의 좌상단 좌표 (i, j)를 기준으로 순회합니다.
  2. 중앙값 체크(최적화): 부분 행렬의 중앙 G[i+1][j+1]이 5가 아니면 마방진이 될 수 없으므로 즉시 건너뜁니다.
  3. 마방진 검증: 9개 요소를 추출해 magicSquare() 함수로 전달하여 다음을 확인합니다.
    • 모든 숫자가 1~9 사이이며 중복이 없는가? (빈도수 배열 활용)
    • 3개 행, 3개 열, 2개 대각선의 합이 모두 15인가?
  4. 카운트 증가: 조건을 만족하면 카운터를 증가시킵니다.

C++ 구현 예제

#include <bits/stdc++.h>
using namespace std;

// 9개 숫자가 마방진을 이루는지 검사
int magicSquare(int a, int b, int c, int d, int e,
                int f, int g, int h, int i) {
    int freq[9] = {0};
    // 인덱스 0~8에 숫자 1~9의 출현 횟수 기록
    freq[a-1]++; freq[b-1]++; freq[c-1]++;
    freq[d-1]++; freq[e-1]++; freq[f-1]++;
    freq[g-1]++; freq[h-1]++; freq[i-1]++;

    // 1~9가 각각 정확히 한 번씩 나왔는지 확인
    for (int k = 0; k < 9; k++) {
        if (freq[k] != 1) return 0;
    }

    // 모든 행, 열, 대각선 합이 15인지 확인
    if ((a + b + c) == 15 && (d + e + f) == 15 && (g + h + i) == 15 &&
        (a + d + g) == 15 && (b + e + h) == 15 && (c + f + i) == 15 &&
        (a + e + i) == 15 && (c + e + g) == 15) {
        return 1;
    }
    return 0;
}

// 그리드 내 마방진 개수 세기
int countSquares(int G[3][4], int R, int C) {
    int count = 0;
    for (int i = 0; i < R - 2; i++) {
        for (int j = 0; j < C - 2; j++) {
            // 중앙이 5가 아니면 스킵
            if (G[i+1][j+1] != 5) continue;

            int isMagic = magicSquare(
                G[i][j],     G[i][j+1],   G[i][j+2],
                G[i+1][j],   G[i+1][j+1], G[i+1][j+2],
                G[i+2][j],   G[i+2][j+1], G[i+2][j+2]
            );
            if (isMagic) count++;
        }
    }
    return count;
}

int main() {
    int Grid[3][4] = { { 4, 3, 8, 4 },
                       { 9, 5, 1, 9 },
                       { 2, 7, 6, 2 } };
    int row = 3, col = 4;
    cout << "Count of Magic Squares in Grid: "
         << countSquares(Grid, row, col);
    return 0;
}

실행 결과

Count of Magic Squares in Grid: 1

시간 복잡도

  • O(R × C): 그리드 크기가 R×C일 때, 각 3x3 윈도우를 상수 시간(O(1))에 검사하므로 전체 선형 시간에 해결됩니다.

핵심 포인트 요약

  • 마방진의 중심은 항상 5이므로, 이를 사전 필터로 사용해 성능을 크게 높일 수 있습니다.
  • 숫자 유일성 검사는 크기 9의 빈도수 배열로 간단히 구현 가능합니다.
  • 행, 열, 대각선 합 검사는 하드코딩된 8개 조건으로 직관적으로 처리합니다.