[HackerRank] Forming a Magic Square (JAVA)

문제

We define a magic square to be an n X n matrix of distinct positive integers from 1 to n² where the sum of any row, column, or diagonal of length n is always equal to the same number: the magic constant.

 

You will be given a 3 X 3 matrix s of integers in the inclusive range [1, 9]. We can convert any digit a to any other digit b in the range [1, 9] at cost of |a - b|. Given s, convert it into a magic square at minimal cost. Print this cost on a new line.

 

Note: The resulting magic square must contain distinct integers in the inclusive range [1, 9].

 

 

입력

Each of the 3 lines contains three space-separated integers of row s[i].

 

 

출력

int: the minimal total cost of converting the input square to a magic square

 

 

제한

s[i][j]는 [1, 9]에 속한다.

 

 

풀이

3 x 3 마방진을 알아야 풀 수 있는 문제였습니다.

 

 

마방진은 가로, 세로, 대각선의 합이 모두 같도록 1 ~ 9의 수들을 모두 배치한 배열을 말합니다. 그렇다면, 우리는 가로, 세로, 대각선에 해당하는 줄의 합이 15라는 사실을 알 수 있습니다.

 

어떻게 알 수 있을까요? 먼저, 1 ~ 9를 모두 배치해야하므로 이들을 싹 더하면 45가 됩니다. 이때, 한 줄에서 배치하는 숫자는 3개이므로 45에서 3을 나누면 15가 됩니다.

 

이제, 서로 다른 세 가지 수를 더해서 15가 되는 경우를 생각해 봅시다. 손으로 계산해도 되고 3중 반복문을 짜서 돌려도 좋습니다. 결과는 아래와 같습니다.

 

 

 

 

여기서 1, 3, 7, 9는 각각 3번씩 나오고, 2, 4, 6, 8은 2번씩 나오는 것을 알 수 있습니다. 그리고 가장 중요한 5는 4번 나오므로 마방진에서 중앙에 위치해야합니다. 중앙에 배치해야 가로, 세로, 오른쪽 대각선, 왼쪽 대각선에 해당하는 연산을 모두 수행할 수 있기때문이죠. 같은 이유로 5 제외 홀수는 5를 기준으로 각각 상하좌우에 배치되어야하고, 짝수는 각각 마방진의 코너에 위치해야합니다.

 

 

이제, 5는 확실히 자리를 잡았고, 홀수와 짝수도 대강 어디에 위치해야하는지 파악했습니다. 그렇다면, 위의 수식을 만족하면서 마방진의 숫자를 넣는 경우의 수를 구해 봅시다.

 

여기서 '1 + 5 + 9'와 '3 + 5 + 7'의 역할이 중요합니다. 이들은 5를 기준으로 상하좌우에 위치해야하기때문이죠. 저는 여기서 전자를 기준으로 설명하겠습니다.

 

5는 중앙에 배치를 하게 되면, 1과 9를 배치하는 경우는 상하 또는 좌우이므로 4가지입니다. 그리고 1과 9가 상하 또는 좌우에 위치해있으므로 3과 7이 들어갈 수 있는 경우는 2가지입니다. 즉, 1과 9를 배치하는 방법은 4가지이고, 각각의 케이스에서 3과 7을 들어갈 수 있는 방법은 2가지이므로 총 경우의 수는 4 X 2 = 8이 됩니다. 따라서 3 X 3 마방진의 개수는 총 8개임을 알 수 있습니다.

 

여기서 의문이 하나 생길 수 있습니다. 저는 홀수만 배치하였을뿐 짝수에 대한 언급은 하지 않았습니다. 하지만, 홀수를 모두 배치하고나면 코너 4군데에만 남는데 짝수들은 15를 만드는 수식에 의하여 자동으로 배치가 됩니다.

 

 

위에서 설명에 의하여 도출한 8가지 마방진은 아래와 같습니다.

 

 

 

 

이제, 우리가 할 일은 한 가지입니다. 문제에서 입력으로 들어온 2차원 배열과 위의 8가지 배열을 각각 비교하면서 cost를 비교하면 됩니다. 그리고 그 중에서 가장 작은 cost를 정답으로 리턴하면 문제를 해결할 수 있습니다.

 

아래는 위 과정을 정리한 소스코드입니다.

 

 

소스코드

 

지적 혹은 조언 환영합니다! 언제든지 댓글로 남겨주세요.