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

C++로 그리드 안의 매직 스퀘어(마법의 정사각형) 개수 구하기

문제 소개

숫자로 채워진 그리드가 주어졌을 때, 이 그리드 안에 존재하는 매직 스퀘어(Magic Square) 부분 격자의 개수를 찾아야 합니다.

여기서 매직 스퀘어란 1부터 9까지의 서로 다른 숫자로 채워진 3×3 크기의 격자로, 모든 행의 합, 모든 열의 합, 그리고 두 대각선의 합이 모두 동일한 값을 가지는 정사각형을 의미합니다. 참고로 1~9를 모두 사용하면 각 줄의 합은 항상 15가 됩니다.

예시

입력이 아래와 같다고 가정해 보겠습니다.

4384
9519
2762

이 경우 출력은 1입니다. 왜냐하면 왼쪽 위 3×3 영역이 매직 스퀘어이기 때문입니다.

438
951
276

확인해 보면 각 행의 합은 4+3+8 = 15, 9+5+1 = 15, 2+7+6 = 15이고, 각 열의 합도 4+9+2 = 15, 3+5+7 = 15, 8+1+6 = 15이며, 두 대각선의 합 역시 4+5+6 = 15, 8+5+2 = 15로 모두 같습니다.

해결 접근 방식

핵심 아이디어는 다음과 같습니다. 1부터 9까지의 숫자를 한 번씩 사용해 만들 수 있는 유효한 매직 스퀘어는 8개뿐이라는 사실을 활용하는 것입니다. 회전과 대칭 변환으로 인해 총 8가지 형태가 나오며, 이를 미리 집합(set)으로 저장해 둡니다.

그다음 그리드를 훑으면서 각 위치에서 3×3 부분 격자를 추출하고, 이를 하나의 9자리 숫자로 변환한 뒤 미리 저장해 둔 집합에 포함되는지 확인합니다. 포함된다면 그것은 유효한 매직 스퀘어입니다.

알고리즘 단계

  • 유효한 매직 스퀘어 8개를 9자리 정수로 표현한 집합을 정의합니다: {816357492, 834159672, 618753294, 672159834, 492357816, 438951276, 294753618, 276951438}
  • 3×3 부분 격자의 각 칸 위치를 계산하기 위한 오프셋 배열 offset(크기 9×2)을 정의합니다: {{-2,-2}, {-2,-1}, {-2,0}, {-1,-2}, {-1,-1}, {-1,0}, {0,-2}, {0,-1}, {0,0}}
  • 정답 변수 ans := 0으로 초기화합니다.
  • i를 2부터 그리드의 행 개수 미만까지 반복합니다.
    • j를 2부터 그리드의 열 개수 미만까지 반복합니다.
      • sum := 0으로 초기화합니다.
      • k를 0부터 8까지 반복하면서 다음을 수행합니다.
        • sum := sum × 10
        • sum := sum + grid[i + offset[k][0]][j + offset[k][1]]
      • ans := ans + (sum이 집합 s에 존재하는지 여부)
  • ans를 반환합니다.

C++ 구현 예제

#include <bits/stdc++.h>
using namespace std;
class Solution {
public:
    int numMagicSquaresInside(vector<vector<int>>& grid) {
        const unordered_set<int> s{816357492, 834159672, 618753294,
            672159834, 492357816, 438951276, 294753618, 276951438};
        const int offset[][2] = {{-2, -2}, {-2, -1}, {-2, 0},
            {-1, -2}, {-1, -1}, {-1, 0},
            { 0, -2}, { 0, -1}, { 0, 0}};
        int ans = 0;
        for(int i = 2; i < grid.size(); i++)
        {
            for(int j = 2; j < grid[0].size(); j++)
            {
                int sum = 0;
                for(int k = 0; k < 9; k++)
                {
                    sum *= 10;
                    sum += grid[i + offset[k][0]][j + offset[k][1]];
                }
                ans += s.count(sum);
            }
        }
        return ans;
    }
};
main(){
    Solution ob;
    vector<vector<int>> v = {{4,3,8,4},{9,5,1,9},{2,7,6,2}};
    cout << (ob.numMagicSquaresInside(v));
}

입력

{{4,3,8,4},{9,5,1,9},{2,7,6,2}}

출력

1

동작 원리 설명

코드가 동작하는 방식을 단계별로 살펴보겠습니다.

  • 집합 초기화: 가능한 매직 스퀘어는 1~9의 숫자를 배치하는 방식 중 극히 일부(8가지)에 불과합니다. 각 매직 스퀘어를 왼쪽 위부터 오른쪽 아래까지 읽어 하나의 9자리 정수로 인코딩하여 unordered_set에 미리 저장해 둡니다.
  • 슬라이딩 윈도우: i와 j는 각각 3×3 부분 격자의 오른쪽 아래 좌표를 나타냅니다. 따라서 루프는 2부터 시작합니다. 오프셋 배열을 사용하면 현재 위치 기준으로 3×3 영역의 9개 칸을 손쉽게 참조할 수 있습니다.
  • 숫자 인코딩: 내부 루프에서 sum에 10을 곱한 후 현재 칸의 값을 더함으로써, 3×3 격자를 하나의 9자리 숫자로 변환합니다.
  • 멤버십 검사: s.count(sum)은 해당 숫자가 유효한 매직 스퀘어 목록에 있으면 1, 없으면 0을 반환하므로 ans에 바로 더할 수 있습니다.

복잡도 분석

  • 시간 복잡도: O(R × C) — 그리드의 각 위치마다 상수 시간(9칸 검사) 작업을 수행합니다.
  • 공간 복잡도: O(1) — 고정된 크기의 집합과 오프셋 배열만 사용합니다.

이처럼 매직 스퀘어의 개수가 유한하다는 수학적 성질을 활용하면, 매번 행·열·대각선의 합을 일일이 검증하는 것보다 훨씬 간결하고 효율적인 코드를 작성할 수 있습니다.