문제

3x3 행렬이 주어지고 이를 마방진으로 바꾸기 위한
최소 비용을 리턴하는 문제이다.

마방진 : 모든 행,열,대각선의 합이 같은 행렬

예시

주어진 행렬

5 3 4
1 5 8
6 4 2

마방진으로 수정

8 3 4
1 5 9
6 7 2

바뀐 숫자
5 -> 8
8 -> 9
4 -> 7

비용 : 5-8 + 8-9 + 4-7 = 7

풀이

3x3 마방진은 총 8개의 경우 밖에 없다.

6 1 8       6 7 2       2 9 4       8 3 4
7 5 3       1 5 9       7 5 3       1 5 9
2 9 4       8 3 4       6 1 8       6 7 2

4 9 2       4 3 8       2 7 6       8 1 6
3 5 7       9 5 1       9 5 1       3 5 7
8 1 6       2 7 6       4 3 8       4 9 2       

이를 전부 배열로 만든다.

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

주어진 행렬과 위 8가지 행렬의 비용을 전부 계산한다.

list_cost = [0,0,0,0,0,0,0,0]

for i in range(8):
      for j in range(3) :
            list_cost[i] += abs(all_magics[i][j][0]-s[j][0])
            list_cost[i] += abs(all_magics[i][j][1]-s[j][1])
            list_cost[i] += abs(all_magics[i][j][2]-s[j][2])

가장 낮은 비용을 리턴한다.

return min(list_cost) 

전체코드

def formingMagicSquare(s):
      all_magics = [
            [[6,1,8],[7,5,3],[2,9,4]],
            [[6,7,2],[1,5,9],[8,3,4]],
            [[2,9,4],[7,5,3],[6,1,8]],
            [[8,3,4],[1,5,9],[6,7,2]],
            [[4,9,2],[3,5,7],[8,1,6]],
            [[4,3,8],[9,5,1],[2,7,6]],
            [[2,7,6],[9,5,1],[4,3,8]],
            [[8,1,6],[3,5,7],[4,9,2]],
      ]

      list_cost = [0,0,0,0,0,0,0,0]

      for i in range(8):
            for j in range(3) :
                  list_cost[i] += abs(all_magics[i][j][0]-s[j][0])
                  list_cost[i] += abs(all_magics[i][j][1]-s[j][1])
                  list_cost[i] += abs(all_magics[i][j][2]-s[j][2])

      return min(list_cost) 

Leave a comment