[python/알고리즘] 이차원 배열로 마방진 만들기

 

2차원 배열을 생성하여 마방진을 만들어보자.

---

 

 

마방진(Magic Square) 이란?

---

일정한 칸 안에 있는 중복을 허용하지 않은 숫자들의 가로, 세로, 대각선의 합이 같은 것을 말한다.

대표적으로 마방진을 활용한 알고리즘 게임으로 스도쿠가 있다.

 

 

Warming up. 간단하게 이차원 배열을 출력해보자.

  
  magicSquare = [
      [1, 14, 14, 4],
      [11, 7, 6, 9],
      [8, 10, 10, 5],
      [13, 2, 3, 15]
  ]

  for i in range(len(magicSquare)):
      print(magicSquare[i])
      

 

---

 

1. 배열 중 행의 합을 출력하는 함수를 만들자.

  
  def checkRow(square):
      for row in range(len(square)):
          sum = 0
          for col in range(len(square)):
              sum += square[row][col]
          print(sum, end=' ')
      print()

  checkRow(magicSquare)
  

-> len(square)는 행의 갯수로 총 4개이다. 

    4 x 4 정사각형의 마방진으로 [0][0] + [0][1] + [0][2] + [0][3] = 출력하며

   [1][0]+[1][1]+[1][2]+[1][3], [2][0]+[2][1]+[2][2]+[2][3], [3][0]+[3][1]+[3][2]+[3][3]까지

   for문을 통해 4개의 행의 합을 각각 출력한다.

 

2. 이번에는 배열 중 열의 합을 출력하는 함수를 만들자.

  
  def checkCol(square):
      for col in range(len(square)):
          sum = 0
          for row in range(len(square)):
              sum += square[row][col]
          print(sum, end=' ')
      print()

  checkCol(magicSquare)
  

-> 위 함수와 같은 원리로 [0][0] + [1][0] + [2][0] + [3][0] ,,, 인덱스 값을 더한다.

 

3. 배열 중 대각선의 합을 출력하는 함수를 만들자.

  
  def checkDiagonal(square):
      sum = 0
      # 왼쪽 시작 대각선
      for d in range(len(square)):
          sum += square[d][d]
      print(sum, end=' ')
      sum = 0
      # 오른쪽 시작 대각선
      for d in range(len(square)):
          d2 = len(square) - 1 - d
          sum += square[d2][d2]
      print(sum)

  checkDiagonal(magicSquare)
  

-> 1. 왼쪽 끝에서 시작하는 대각선의 합을 구한다. [0][0]+[1][1]+[2][2]+[3][3]

    2. 오른쪽 끝에서 시작하는 대각선의 합을 구한다. [0][3]+[1][2]+[2][1]+[3][0]

 

4. 위의 함수를 활용하여 마방진을 체크하는 함수를 만들자.

  
  def checkMagic(square):
      magic = 0
      for i in range(len(square)):
          magic += square[0][i]
      for i in range(len(square)):
          rsum = 0
          csum = 0
          for j in range(len(square)):
              rsum += square[i][j]
              csum += square[j][i]
          if rsum != magic or csum != magic :
              return False
      dsum = 0
      d2sum = 0
      for d in range(len(square)):
          d2 = len(square) -1 -d
          dsum += square[d][d]
          d2sum += square[d2][d2]
      if dsum != magic or d2sum != magic:
          return False
      return True

  print(checkMagic(magicSquare))
  

 

Q. n * n 마방진 만들어보자. (단, n은 홀수이다.)

A.

  
  def makeMagicSquare(n):
      # 배열 초기화
      square = [ [0] * n for _ in range(n) ]
      row = 0
      col = n // 2
      for k in range(1, n*n+1):  # 1부터 25까지
          square[row][col] = k
          row -= 1
          if row < 0 :
              row += n
          col -= 1
          if col < 0 :
              col += n
          if square[row][col] > 0 :
              row = ( row + 2 ) % n
              col = ( col + 1 ) % n
      return square

  print('\n내가 만든 마방진 출력')
  magicSquare2 = makeMagicSquare(5)
  for row in magicSquare2:
      print(row)

  # 마방진 체크
  print(checkMagic(magicSquare2))
  

-> 1. 첫번째 열의 가운데 행을 1로 채운다.
    2. 해당 위치에서 한 칸 왼쪽, 한 칸 위쪽으로 이동하여 다음 숫자를 채운다.
      - 칸을 벗어나면 그 줄의 반대쪽으로 이동한다.
    3. 이동할 위치에 숫자가 이미 있으면 한 칸 아래로 이동한다.
    4. 이동할 위치에 숫자가 없으면 이동해서 숫자를 채운다.

 

 

출처 : Youtube 주니온TV 아무거나연구소의 코린아, 코딩하자! with 파이썬