[백준] 1307 (마방진)

# 시작: 첫 행의 가운데 열에 1 배치
x, y = 0, n // 2

for i in 1 to n*n:
    grid[x][y] = i
    nx, ny = (x-1) % n, (y+1) % n  # ↗ 이동
    if grid[nx][ny] != 0:           # 충돌!
        x = (x+1) % n              # ↓ 아래로
    else:
        x, y = nx, ny

# 1~N² 순서대로 채우기
ans[i][j] = i * N + j + 1

# 십자(cross) 영역을 점대칭 교환
for i in range(N // 4):              # 상단 Q행
    for j in range(N//4, 3*N//4):    # 중앙 열
        swap(ans[i][j], ans[N-1-i][N-1-j])     # 상↔하
        swap(ans[j][i], ans[N-1-j][N-1-i])     # 좌↔우

왜 동작하는가?

순서대로 채운 격자에서 (i, j)의 값과 점대칭 위치 (N-1-i, N-1-j)의 값의 합은 항상 N² + 1입니다. 교환 시 두 위치를 포함하는 행·열 쌍의 합이 보존되며, 십자 패턴이 각 행·열에서 정확히 절반의 셀만 교환되도록 보장합니다.

오프셋 승수 배치 규칙:

# 상반부 (i < N/2): k = [3, 0, 2, 1]
# 하반부 (i ≥ N/2): k = [0, 3, 1, 2]
#
# 좌측 절반 (cols 0..N/2-1):
#   일반 행: [0, N/4)열 → k[0],  [N/4, N/2)열 → k[1]
#   특수 행 (i % (N/2) == N/4):
#     0열 → k[1], [1, 1+N/4)열 → k[0], 나머지 → k[1]
#
# 우측 절반 (cols N/2..N-1):
#   [N/2, N-N/4]열 → k[2],  [N-N/4+1, N)열 → k[3]
#
# 최종: ans[i][j] = 승수[i][j] × n² + M[i%n][j%n]

왜 동작하는가?

오프셋 배치는 각 행·열에서 승수 0, 1, 2, 3이 각각 정확히 n번(= N/2번) 등장하도록 설계되었습니다. 따라서 오프셋의 행/열 합이 균일해지고, 4개 사분면에 복사된 홀수 마방진의 합 성질도 보존되므로 전체가 마방진이 됩니다.

핵심 포인트

세 방법 모두 시간·공간 복잡도가 O(N²)이며, N ≤ 300 범위에서 충분히 빠릅니다. 입력 N의 형태(홀수 / 4의 배수 / 4k+2)에 따라 적절한 방법을 선택하면 됩니다.

n = N  # N은 홀수
odd = [[0] * n for _ in range(n)]
x, y = 0, n // 2          # 첫 행 가운데에서 시작

for i in range(1, n * n + 1):
    odd[x][y] = i
    nx = (x - 1) % n       # ↗ 위로
    ny = (y + 1) % n       # ↗ 오른쪽으로
    if odd[nx][ny] != 0:    # 충돌 시
        x = (x + 1) % n    # 대신 ↓ 아래로
    else:
        x, y = nx, ny