실력키우기 마방진(JAVA)

2074 : 마방진

제한시간: 1Sec    메모리제한: 64mb
해결횟수: 1029회    시도횟수: 1429회    Special Judge

홀수 정사각형의 크기를 입력 받은 후, 가로 세로 대각선의 합이 일정한 마방진을 출력하는 프로그램을 작성하시오.

마방진이란 1부터 N*N까지의 숫자를 한 번씩만 써서 정사각형에 배치하여 가로와 세로, 그리고 대각선의 합이 같도록 하는 것이다.

다음의 순서에 따라 각 위치에 차례대로 값을 넣는다.
1. 첫 번째 숫자인 1을 넣는 위치는 첫 번째 행 가운데이다.
2. 숫자가 N의 배수이면 바로 아래의 행으로 이동하여 다음의 수를 넣고
3. 그렇지 않으면 왼쪽 위로 이동하여 다음의 숫자를 넣는다. 만약 행이 첫 번째를 벗어나면 마지막 행으로 이동하고, 열이 첫 번째를 벗어나면 마지막 열로 이동한다.

 

1. 첫 번째 행 가운데(1,2)에 1을 넣는다.
2. 왼쪽 위로 이동하면 (0,1)인데 행의 위치가 처음을 벗어났으므로 마지막행(3,1)의 위치로 이동하여 2를 넣는다.
3. 왼쪽 위로 이동하면 (2,0)인데 열의 위치가 처음을 벗어났으므로 마지막열(2,3)의 위치로 이동하여 3을 넣는다.
4. 배열에 넣은 값(3)이 N의 배수이므로 바로 아래행으로(3,3) 이동하여 4를 넣는다.
5. 왼쪽 위로 이동하여 (2,2) 5를 넣는다.
6. 왼쪽 위로 이동하여 (1,1) 6를 넣는다.
7. 배열에 넣은 값(6)이 N의 배수이므로 바로 아래행으로(2,1) 이동하여 7을 넣는다.
8. 왼쪽 위로 이동하면 (1,0)인데 열의 위치가 처음을 벗어났으므로 마지막열(1,3)의 위치로 이동하여 8을 넣는다.
9. 왼쪽 위로 이동하면 (0,2)인데 행의 위치가 처음을 벗어났으므로 마지막행(3,2)의 위치로 이동하여 9를 넣는다.

 

정사각형의 크기 n(2부터 100사이의 홀수)을 입력받는다.

위에서 언급한 형태로 정사각형의 내부 숫자를 차례로 채운 후의 모습을 출력한다. 
숫자 사이는 공백으로 구분한다.

[Copy] 3

[Copy] 6 1 8 7 5 3 2 9 4

[Copy] 5

[Copy] 15 8 1 24 17 16 14 7 5 23 22 20 13 6 4 3 21 19 12 10 9 2 25 18 11

?

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61

/**************************************************************     Problem: 2074     User: a132034     Language: Java     Result: Success     Time:271 ms     Memory:10680 kb ****************************************************************/     import java.util.Scanner;   public class Main{     public static void main(String[] args) {         Scanner sc = new Scanner(System.in);         int N = sc.nextInt();                   /*          * 마방진에 숫자를 넣는 순서.          * 첫 숫자인 1은 -> 첫행 가운데          * N의 배수일 경우 바로 아래 행으로 내려가 다음 수를 넣는다.          * 그렇지 않다면 왼쪽 위로 이동하여 다음 숫자를 넣는다. 만약 행이 첫 번째를 만나면 마지막 행으로 이동한다.          * 열이 첫 번째를 만나면 마지막 열로 이동한다.          * */               int[][] magicSquare = new int[N][N];                   int x = 0, y = N/2;         magicSquare[x][y] = 1;                   for(int i = 1; i < N*N; ++i)         {               if((i+1)%N == 1){                 x++;                 if(x == N)                     x = 0;                 magicSquare[x][y] = i+1;             }else{                 x--;                 if(x == -1)                     x = N-1;                                   y--;                 if(y == -1)                     y = N-1;                                   magicSquare[x][y] = i+1;             }           }                   for(int i = 0 ; i < N; ++i)         {             for(int j = 0 ; j < N; ++j)                 System.out.print(magicSquare[i][j] + " " );             System.out.println();         }                         } }

도움말

01 void fill()
 02 {
 03     int x = 1;                    // 행 - 처음에는 1 
 04     int y = n / 2 + 1;            // 열 - 초기값 중앙
 05     int i;                        // 배열에 순서대로 채울 값 (for 문에 사용할 변수)
 06     int end = n * n;              // 배열에 채울 마지막 값
 07 
 08     for (i = 1; i <= end; i++) {  // 배열에 채울 값 1부터 end까지
 09         arr[x][y] = i;            // i를 배열의 현재 위치에 넣는다.
 10         if (i % n == 0) {         // 만약 현재의 수가 n의 배수이면 아래로 이동
 11             x++;                 
 12         }
 13         else {
 14             x--, y--;             // 왼쪽 위로 이동
 15             if (x < 1) x = n;     // x가 0이면 n으로
 16             if (y < 1) y = n;     // y가 0이면 n으로
 17         }
 18     }
 19 }

<코드분석>
 06~07 : 행과 열을 처음에 넣어야 할 위치로 초기화 하고
 11~21 : 1부터 n * n 까지 각각 넣어야 할 위치에 차례대로 채워나가는 프로그램 
 13~15 : i가 n의 배수이면 아래로 이동하고
 16~20 : 그렇지 않으면 왼쪽 위로 이동을 한 후 범위를 벗어나면 끝으로 이동시킨다.

<코드>
 01 /* 채워야 할 위치(x, y)와 값(num)을 전달받아                          */
 02 /* 배열에서 해당 위치에 값을 넣고 다음의 위치와 값을 호출하는 재귀함수 */
 03
 04 void fill(int x, int y, int num)
 05 {
 06    if(num > n * n) return;                     // 수가 범위를 벗어나면 종료
 07    if(x < 1) x = n;                              // x가 0이면 n으로
 08    if(y < 1) y = n;                              // y가 0이면 n으로
 09    arr[x][y] = num;                             // 배열 채우기
 10    if(num % n == 0) fill(x + 1, y, num + 1);    // num이 n의 배수이면 바로 아래 호출
 11    else fill(x - 1, y - 1, num + 1);             // 아니면 왼쪽 위 호출 
 12 }

<코드분석>
 이 함수는 전달받은 위치 한곳만 채우고 다음 위치를 호출하는 재귀함수이다.
 재귀함수 특성상 자신이 처리해야 할 위치 한 곳만 처리하고 (09) 
 다음 위치를 호출하면 임무가 끝난다. (10~11)
 다음 위치를 호출할 때 i가 n의 배수가 아니면 무조건 왼쪽 위를 호출했기 때문에 (11)
 범위를 벗어난 경우 마지막 위치로 바꾸어 주는 작업이 필요하다. (07~08)
 범위를 벗어나는 호출이 들어오면 모든 작업이 끝나게 된다. (06)
 처음에는 첫 번째 행 중앙에 1을 채워야 하므로 메인에서는 아래와 같이 호출해야 한다.
 fill(1, n / 2 + 1, 1);

사실 문제에 설명이 다 나와있어서 도움말을 보지 않아도.. 푸는데 어려움은 없었다. 

첫 숫자를 넣고 시작했고, 배수일 경우 아래 행으로 내려가는 것은 배수일 경우의 다음 숫자이므로 N으로 나눈 나머지가 1일 경우로 하였다.

나머지는 크게 어려운 것은 없었다.