문제

아래와 같이 가로/세로/대각선의 합계가 모두 같은 행렬을 magic-square 라고 한다.

8 3 4
1 5 9
6 7 2

특정 3x3 행렬이 주어질 때 아래와 같이 magic-square 로 변환할 수 있다.

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

이 경우 변경이 필요한 숫자는 5,8,4 뿐이며 변경에 발생한 비용은 아래와 같이 계산할 수 있다.

|5-8| + |8-9| + |4-7| = 7

위 예제의 변환 비용은 7이 된다.


미션) 1~9의 자연수를 요소로 같는 임의의 3x3 행렬이 주어질 때 이를 magic-square 로 변환하기 위한 최소 비용을 구하는 함수를 작성하라


풀이 컨셉

3x3 행렬에서 magic-square 의 종류는 8의 위치와 방향에 따라 아래 8가지로 분류된다.

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

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

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

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

주어진 3x3 행렬에 대하여 위 8가지 경우에 대한 비용을 각각 계산하고 그 중 최소값을 리턴한다


js코드

function formingMagicSquare(s) {
    var ms = [
        [8,3,4,1,5,9,6,7,2],
        [8,1,6,3,5,7,4,9,2],
        [4,3,8,9,5,1,2,7,6],
        [6,1,8,7,5,3,2,9,4],
        [2,7,6,9,5,1,4,3,8],
        [2,9,4,7,5,3,6,1,8],
        [6,7,2,1,5,9,8,3,4],
        [4,9,2,3,5,7,8,1,6]
    ];
    
    var arr = [];
    for(var i=0; i<3; i++){
        for(var j=0; j<3; j++){
            arr.push(s[i][j]);
        }
    }
    
    var minsum = 1000000;       // 충분히 큰값 임의 세팅
    
    ms.forEach(msarr => {
        var sum = msarr.reduce((a, v, i) => a + Math.abs(v - arr[i]), 0);
        if(sum < minsum){
            minsum = sum;
        }
    });
    
    return minsum;
}

formingMagicSquare([
    [4, 9, 2],
    [3, 5, 7],
    [8, 1, 5]
])


코드 리뷰

  • 비용 계산을 쉽게 하기 위해 2차원 배열을 1차원 배열로 serialize 하였다
  • 보다 스마트한 방법이 있을 것 같지만 경우의 수가 많지 않은 예제라 하드코딩된 데이터를 이용했다. 하지만 마음이 편치 않다.
  • forEach 안에서 인자와 변수들의 구별을 명확히 하지 않으면 오류가 발생할 수 있으니 주의한다
    • 실제 코딩시 msarr 대신 arr이름을 사용했다가 앞서 정의된 arr 변수와의 충돌로 잘못된 결과가 나왔었다.


Ref.

https://www.hackerrank.com/challenges/magic-square-forming/problem