🧩 초보자용 가이드 'Largest Magic Square' – LeetCode 1895 (C++, Python, JavaScript)

Source: Dev.to

문제 설명

그리드에서 패턴을 찾는 것은 알고리즘 사고에서 고전적인 도전 과제입니다.
이 문제에서는 모든 행, 열, 그리고 두 주요 대각선의 합이 정확히 동일한 가능한 가장 큰 부분 그리드를 찾는 것이 목표입니다.

주어진 내용

• m × n 정수 그리드.
• 매직 스퀘어는 모든 행, 모든 열, 그리고 두 대각선의 합이 같은 k × k 부분 그리드입니다.

목표

그리드 안에 숨겨진 매직 스퀘어 중 최대 변의 길이 k를 반환하세요.

예시

예시 1

Input:  grid = [[7,1,4,5,6],
               [2,5,1,6,4],
               [1,5,4,3,2],
               [1,2,7,3,4]]
Output: 3

설명 – 가장 큰 마법 정사각형의 크기는 3입니다. 이 정사각형의 모든 행 합, 열 합, 대각선 합은 모두 12가 됩니다.

• 행 합: 5+1+6 = 5+4+3 = 2+7+3 = 12
• 열 합: 5+5+2 = 1+4+7 = 6+3+3 = 12
• 대각선 합: 5+4+3 = 6+4+2 = 12

예시 2

Input:  grid = [[5,1,3,1],
               [9,3,3,1],
               [1,3,3,8]]
Output: 2

제약 조건

• m == grid.length
• n == grid[i].length
• 1 ≤ m, n ≤ 50
• 1 ≤ grid[i][j] ≤ 10⁶

직관

브루트‑포스 해결책은 모든 가능한 크기의 모든 정사각형을 검사하고 행, 열, 대각선의 합을 수동으로 계산합니다. 이는 많은 작업을 반복하게 됩니다.

효율적으로 만들기 위해 접두합(누적 합계)을 사용합니다.
예를 들어, 열 10까지와 열 5까지의 행 합을 알고 있다면, 5와 10 사이의 합은 두 값의 차이만큼이면 됩니다.

각 셀에 대해 네 개의 접두합 표를 미리 계산합니다:

이 표들을 사용하면 k × k 정사각형이 마법 정사각형인지 확인하는 작업이 몇 번의 상수 시간 뺄셈으로 줄어듭니다.
가능한 가장 큰 변의 길이 min(m, n)부터 차례로 검색합니다; 조건을 만족하는 첫 번째 크기가 답이 됩니다.

솔루션 코드

C++

class Solution {
public:
    // Check whether the k×k square with top‑left corner (r, c) is magic
    bool isMagic(const vector>>& pref,
                 int r, int c, int k) {
        // target sum = main diagonal of the square
        int target = pref[r + k][c + k][2] - pref[r][c][2];

        // anti‑diagonal must match
        if (target != pref[r + k][c + 1][3] - pref[r][c + k + 1][3])
            return false;

        // each row sum must match
        for (int i = r; i >& grid) {
        int m = grid.size(), n = grid[0].size();

        // pref[i][j] = {row, col, diag, anti‑diag} sums up to (i‑1, j‑1)
        vector>> pref(m + 1,
                                          vector>(n + 2, {0,0,0,0}));

        for (int i = 1; i = 2; --k) {
            for (int i = 0; i + k  int:
        m, n = len(grid), len(grid[0])

        # pref[i][j] = [row, col, diag, anti_diag] sums up to (i‑1, j‑1)
        # extra padding (n+2) simplifies anti‑diagonal indexing
        pref = [[[0] * 4 for _ in range(n + 2)] for _ in range(m + 1)]

        for i in range(1, m + 1):
            for j in range(1, n + 1):
                val = grid[i - 1][j - 1]
                pref[i][j][0] = pref[i][j - 1][0] + val          # row
                pref[i][j][1] = pref[i - 1][j][1] + val          # column
                pref[i][j][2] = pref[i - 1][j - 1][2] + val      # main diagonal
                pref[i][j][3] = pref[i - 1][j + 1][3] + val      # anti‑diagonal

        # helper to test a k×k square with top‑left corner (r, c)
        def is_magic(r: int, c: int, k: int) -> bool:
            target = pref[r + k][c + k][2] - pref[r][c][2]      # main diagonal
            if target != pref[r + k][c + 1][3] - pref[r][c + k + 1][3]:
                return False

            # rows
            for i in range(r, r + k):
                if pref[i + 1][c + k][0] - pref[i + 1][c][0] != target:
                    return False
            # columns
            for j in range(c, c + k):
                if pref[r + k][j + 1][1] - pref[r][j + 1][1] != target:
                    return False
            return True

        for k in range(min(m, n), 1, -1):
            for i in range(m - k + 1):
                for j in range(n - k + 1):
                    if is_magic(i, j, k):
                        return k
        return 1

Python

3] + val

def is_magic(r, c, k):
    # Target sum from the main diagonal
    target = pref[r + k][c + k][2] - pref[r][c][2]

    # Check anti-diagonal
    if target != pref[r + k][c + 1][3] - pref[r][c + k + 1][3]:
        return False

    # Check all rows
    for i in range(r, r + k):
        if pref[i + 1][c + k][0] - pref[i + 1][c][0] != target:
            return False

    # Check all columns
    for j in range(c, c + k):
        if pref[r + k][j + 1][1] - pref[r][j + 1][1] != target:
            return False

    return True

# Check from largest possible side length downwards
for k in range(min(m, n), 1, -1):
    for i in range(m - k + 1):
        for j in range(n - k + 1):
            if is_magic(i, j, k):
                return k
return 1

JavaScript

/**
 * @param {number[][]} grid
 * @return {number}
 */
var largestMagicSquare = function (grid) {
    const m = grid.length;
    const n = grid[0].length;

    // Create prefix

작동 방식 – 단계별

1. 접두사 테이블 구축 – O(m·n) 시간, O(m·n) 추가 공간.
2. 측면 길이를 큰 것부터 작은 것으로 순회.
3. 가능한 각 좌상단 코너에 대해 추출:
   • 주 대각선 합,
   • 반대 대각선 합,
   • 각 행 합,
   • 각 열 합
     를 접두사 테이블의 상수 시간 뺄셈만으로 수행.
4. 모든 검사를 통과하는 첫 번째 크기가 답이다.

첫 번째 유효한 크기에서 멈추기 때문에 전체 복잡도는
O(m·n·min(m, n)) (최악의 경우에도 m, n ≤ 50이면 여전히 빠름).