[해커랭크] Forming a Magic Square

문제링크

Forming a Magic Square | HackerRank

이 문제에서는 3x3 행렬을 매직 스퀘어로 변환하는 최소 비용을 찾는 것이 목표입니다. 매직 스퀘어는 각 행, 열, 대각선의 합이 동일한 상수값(매직 상수)이 되는 1부터 9까지의 서로 다른 양의 정수로 구성된 행렬입니다.

 

- 주어진 행렬의 숫자는 1부터 9까지의 범위에 있습니다.

- 행렬의 숫자를 다른 숫자로 변환하는 데 드는 비용은 1입니다.

- 주어진 행렬을 매직 스퀘어로 변환하는 데 필요한 최소 비용을 계산해야 합니다.

- 결과적인 매직 스퀘어는 1부터 9까지의 서로 다른 정수를 포함해야 합니다.

 

풀이 :

function formingMagicSquare(s) {
    const magicSquares = [
        [[8, 1, 6], [3, 5, 7], [4, 9, 2]],
        [[6, 1, 8], [7, 5, 3], [2, 9, 4]],
        [[4, 9, 2], [3, 5, 7], [8, 1, 6]],
        [[2, 9, 4], [7, 5, 3], [6, 1, 8]],
        [[8, 3, 4], [1, 5, 9], [6, 7, 2]],
        [[4, 3, 8], [9, 5, 1], [2, 7, 6]],
        [[6, 7, 2], [1, 5, 9], [8, 3, 4]],
        [[2, 7, 6], [9, 5, 1], [4, 3, 8]],
    ];

    let minCost = Infinity;
    for (let magic of magicSquares) {
        let cost = 0;
        for (let i = 0; i < 3; i++) {
            for (let j = 0; j < 3; j++) {
                cost += Math.abs(s[i][j] - magic[i][j]);
            }
        }
        minCost = Math.min(minCost, cost);
    }
    return minCost;
}

모든 가능한 3x3 매직 스퀘어를 생성한 후 각 매직 스퀘어와 주어진 행렬 간의 비용을 계산합니다. 비용은 두 행렬의 동일 위치에 있는 숫자들 간의 차이의 절대값의 합입니다. 모든 매직 스퀘어에 대해 계산된 비용 중 최소값을 찾아 반환합니다.

 

다른 풀이 :

function isMagicSquare(square) {
    const sum = 15
    const uniqueNumbers = new Set(square.flat());
    if (uniqueNumbers.size !== 9) return false; 

    for (let i = 0; i < 3; i++) {
        if (square[i][0] + square[i][1] + square[i][2] !== sum) return false; 
        if (square[0][i] + square[1][i] + square[2][i] !== sum) return false; 
    }
    
    if (square[0][0] + square[1][1] + square[2][2] !== sum) return false;
    if (square[0][2] + square[1][1] + square[2][0] !== sum) return false;

    return true;
}

function generateMagicSquares(){
    const result = [];
    
    function generator(arr, row) {
        if(row === 3){
            if(isMagicSquare(arr)){
                result.push(JSON.parse(JSON.stringify(arr)))
                return
            }
            return
        }
        
        for(let i=1; i<=9;i++){
            if(!arr.flat().includes(i)){
                arr[row].push(i)
                if(arr[row].length === 3){
                    generator(arr, row+1)
                }else{
                    generator(arr)
                }
                arr[row].pop()
                
            }
        }
    }
    
    generator([[],[],[]], 0)
    return result
}

function formingMagicSquare(s) {
   const magicSquares = generateMagicSquares();
    let minCost = Infinity;
    
    for (let magic of magicSquares) {
        let cost = 0;
        for (let i = 0; i < 3; i++) {
            for (let j = 0; j < 3; j++) {
                cost += Math.abs(s[i][j] - magic[i][j]);
            }
        }
        minCost = Math.min(minCost, cost);
    }

    return minCost;
}

모든 가능한 매직 스퀘어를 직접 작성하지 않고 백트래킹 방법으로 조합들을 생성합니다.
(단, 계산 시간이 길어지므로 시간이 제한된 경우라면 위 풀이처럼 미리 매직 스퀘어를 정의해서 풀이하는 것도 좋을 듯)