마방진

문제

• 매직 스퀘어? 마방진
  • s = n x n 행렬로, 각 행의 합, 각 열의 합, 각 대각선의 합이 모두 같은 행렬
  • \[\text{행렬의 각 수는 서로 다른 수로,}\; 1 \;to\; {n^2}\]
• \[\text{3 X 3 행렬을 매개변수로 받으며 서로 다른 각 정수는}\;[1, 9]\; \text{ 범위에 속한다}\]
• \[[1, 9]\text{ 범위 내의 정수 a를 다른 b로 변환 시 } \lvert a - b\rvert\;\text{비용이 든다}\]
• s가 주어졌을 때, 최소한의 비용으로 마방진으로 바꿔라

생각

1st

• 처음에는 행/열/대각선의 합을 반복문을 돌면서 구하고, 합이 맞지 않은 위치만 변경하려고 했다
• 가령 아래 샘플 케이스에서 [0][1], [1][2], [2][1]의 위치만 바꾸면 되는 거 아닌가라고 간단하게 생각

[
    [5, 3, 4],
    [1, 5, 8],
    [6, 4, 2]
]

[
    [8, 3, 4],
    [1, 5, 9],
    [6, 7, 2]
]

• 하지만 아래 같은 행렬이 넘어오면 모든 위치가 변경되어야 하는데, 그럼 어떤 때가 최소 비용일까?

[
    [1, 2, 1],
    [1, 1, 3],
    [1, 3, 1]
]

• 너무 막연하기에 다르게 생각해 봤다

2nd

• 마방진으로 만들려는 행렬은 결국 n X x, 여기서는 9개 수의 나열 아닌가? 그렇다면 9개 수의 모든 조합을 만들어서 그중에서 각 행, 각 열, 각 대각선의 합이 같은 것들만 추려내면 되지 않을까?
• permutation 알고리즘 필요

순열

• 수를 나열하는 것
• 수를 나열하는 경우의 수는, n개의 원소에 대해 n!

케이스

1 2 3 = 3! = 6

"1" 2 3
"1" 3 2

"2" 1 3
"2" 3 1

"3" 1 2
"3" 2 1

코드

# 구현