magic square

얼마 전에 온라인 코딩 테스트 문제 중의 하나로 magic square 문제를 풀었습니다.

 

magic square가 무슨 뜻인지 찾아봤는데 마방진을 뜻하는 거였더군요.

 

문제 설명을 먼저 드리면

 

3 X 3 배열을 입력하여 가로, 세로, 대각선의 숫자들을 더한 값이 모두 같은 값을 갖게 하는 것인데,

 

입력한 배열이 마방진의 조건에 맞게 하기 위해 배열 값을 교환했을 때의 최소 비용을 구하는 것입니다.

 

예를 들어 다음과 같이 입력했을 때의 최솟값을 구하려면

 

<입력한 배열>

5 3 4

1 5 8

6 4 2

 

다음과 같이 배열을 교환할 수 있습니다.

 

<교환한 배열>

8(5->8) 3 4

1 5 9(8->9)

6 7(4->7) 2

 

위와 같이 교환한 배열에서 최소비용을 구하게 되면

 

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

 

최소비용 7을 구할 수 있습니다.

 

근데 과연 이렇게 구한 값이 최소 비용인지 의문이 들 수 있습니다.

 

하지만 3 X 3 마방진의 경우는 다음과 같이 8가지로 정해져 있기 때문에 최소비용인지 확인할 수 있습니다.

 

1. {6,7,2}, {1,5,9}, {8,3,4}}
2. {{4,9,2}, {3,5,7}, {8,1,6}}
3. {{8,1,6}, {3,5,7}, {4,9,2}}
4. {{6,1,8}, {7,5,3}, {2,9,4}}
5. {{2,9,4}, {7,5,3}, {6,1,8}}
6. {{8,3,4}, {1,5,9}, {6,7,2}}
7. {{4,3,8}, {9,5,1}, {2,7,6}}
8. {{2,7,6}, {9,5,1}, {4,3,8}}

(총 8가지)

 

그러므로 위의 8가지 경우를 루프 돌아서 입력한 배열의 최소비용을 구할 수 있습니다.

 

소스 코드

 

8가지 경우를 각각 루프 돌아서 최소 비용을 구하는 소스입니다.

 

3 X 3 마방진의 경우의 수가 정해져 있다는 것을 모를 경우

 

문제를 푸는데 어렵지 않을까 생각이 듭니다.

 

경우의 수가 있다는 것을 알게 되면 허무한 문제인 거 같고요.

 

제 생각에는 좋은 문제인 거 같지는 않습니다.