[HackerRank] Forming a Magic Square (마방진) Implementation 문제

 

문제

마법의 정사각형(Magic Square)은 3x3 크기의 정사각형 그리드로 구성되며,

숫자 1부터 9까지의 모든 숫자가 한 번씩 나타나고, 각 행(row), 열(column),

그리고 대각선(diagonal)의 숫자 합이 모두 동일한 값을 가집니다.

주어진 3x3 숫자 그리드를 최소한의 비용으로 마법의 정사각형으로 변환해야 합니다.

 

변환 비용은 각 숫자를 다른 숫자로 바꾸는 데 드는 비용이며, 이 비용은 두 숫자의 차이만큼 증가합니다.

예를 들어:

4 8 2
4 5 7
6 1 6

이 그리드를 마법의 정사각형으로 바꾸는 최소 비용을 계산해야 합니다.

 

입력:

• 3x3 크기의 정수 그리드가 주어집니다.

 

출력:

• 마법의 정사각형으로 변환하기 위한 최소 비용을 출력합니다.

 

문제 해결 전략

이 문제를 해결하기 위해 먼저 가능한 모든 3x3 마방진 개념을 알아야 합니다. 

• 마방진의 크기는 일반적으로 n×n 크기의 정사각형 형태로 이루어져 있습니다.
• 마방진의 모든 행, 열, 대각선에서의 합이 동일하게 되는 값입니다.
• 3×3 마방진의 경우 마법 상수는 항상 15입니다.
• 3x3 크기의 마법의 정사각형은 총 8가지가 있습니다. 

아래는 가능한 3x3 마법의 정사각형입니다.

[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]

 

이제 이 8개의 마법의 정사각형 중 주어진 그리드를 각 마법의 정사각형과 비교하여 변환 비용을 계산합니다.

최종적으로 가장 작은 변환 비용을 구하면 됩니다.

 

 

풀이코드

def formingMagicSquare(s):
    # 가능한 3x3 마법의 정사각형들
    magic_squares = [
        [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]
    ]
    
    # sum()의 인자는 숫자리스트 또는 숫자이터러블(iterable)을 인수로 받음
    # 따라서 현재 2차원 리스트를 1차원 리스트로 변환, 평탄화(flatten) 작업
    s = sum(s, []) # [4, 8, 2, 4, 5, 7, 6, 1, 6]
    
    # 각 마법의 정사각형과 비교하여 최소 비용 계산
    min_cost = float('inf')
    for magic in magic_squares:
        cost = sum(abs(s[i] - magic[i]) for i in range(9))
        min_cost = min(min_cost, cost)
    
    return min_cost

# 예시 실행
s = [
    [4, 8, 2],
    [4, 5, 7],
    [6, 1, 6]
]

print(formingMagicSquare(s))  

# 출력: 4

 

인자로 주어진 [4, 8, 2, 4, 5, 7, 6, 1, 6] 값과 각각 8개의 마방진으로 교체시 비용을 비교한다.

최소 비용을 계산하기 위해 다른 모든 마법의 정사각형과 비교한 후 최솟값을 선택합니다.

- 주어진 정사각형
4 8 2
4 5 7
6 1 6


- 마법의 정사각형 중 하나와 비교
8 1 6
3 5 7
4 9 2

이와 비교하면:
4 → 8 (비용 4)
8 → 1 (비용 7)
2 → 6 (비용 4)
4 → 3 (비용 1)
5 → 5 (비용 0)
7 → 7 (비용 0)
6 → 4 (비용 2)
1 → 9 (비용 8)
6 → 2 (비용 4)

총 비용: 4 + 7 + 4 + 1 + 0 + 0 + 2 + 8 + 4 = 30