마방진 > 문제은행

본문 바로가기


실력키우기 도형만들기

2074 : 마방진

제한시간: 1000 ms    메모리제한: 64 MB
해결횟수: 1490 회    시도횟수: 2017 회    Special Judge



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


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


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


e3050b66a1b29a01767400d7560a4131_1449726
 


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


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);



HancomEducation E-mail : hancomc@hotmail.com, comkiwer@naver.com Tel : 070-7163-5782 FAX : 031-388-0996 정올소개 이용약관 개인정보처리방침
경기도 안양시 동안구 호계동 1065-10 협성골드프라자 601호, 경기도 안양시 동안구 평촌대로 109 협성골드프라자 601호
Copyright@2010-2015 jungol. All right reserved.