달팽이사각형 > 문제은행

본문 바로가기


실력키우기 도형만들기

1707 : 달팽이사각형

제한시간: 1000 ms    메모리제한: 64 MB
해결횟수: 2362 회    시도횟수: 4559 회   



정사각형의 크기를 입력 받은 후 시계방향으로 돌면서 다음과 같은 형태로 출력하는 프로그램을 작성하시오.


< 처리조건 >
(1) 가장 왼쪽 위의 좌표부터 차례로 숫자를 대입시킨다.
(2) 오른쪽으로 채워 나가다가 끝이면 다시 아래 → 왼쪽 → 위 →오른쪽의 순으로 모두 채워질때까지 반복한다.


e3050b66a1b29a01767400d7560a4131_1449725
 


 


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


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

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


[Copy]
2
[Copy]
1 2
4 3


<생각하기> 
처음에는 (1, 1)의 위치에 숫자 1을 담으면 된다.
그리고 오른쪽으로 이동하면서 차례대로 숫자를 늘려가면서 n번을 반복하여 채워나가면 된다.
그런데 만약 다음과 같이 숫자를 먼저 채우고 오른쪽으로 이동을 한다면 가장 오른쪽을 채운 후 범위를 벗어나게 된다. 
    arr[x][y] = num++;
    y++;

그러므로 아래와 같이 오른쪽으로 먼저 이동을 한 후에 숫자를 채우도록 해야 마지막 위치에서 숫자를 채우고 멈추게 된다.
    y++;
    arr[x][y] = num++;

그러기 위해서는 y를 0으로 초기화 하면 된다.

위의 두 문장을 한문장으로 쓰고 싶다면 아래와 같이 쓰면 된다.
 arr[x][++y] = num++;

오른쪽으로 이동이 끝난 후에는 아래쪽 ? 왼쪽 ? 위쪽으로 같은 방법으로 채워나가는 작업을 반복하면 된다. 그런데 각각의 이동 횟수가 조금씩 줄어들다가
더 이상 이동할 곳이 없다면 즉, 이동할 횟수가 0이 되면 끝나게 된다.

n이 5라고 가정을 하고 이렇게 각 방향으로 이동하는 횟수를 표로 나타내면 다음과 같다.


표를 보면 알겠지만 아래쪽으로 이동하는 횟수는 오른쪽보다 한번 줄어들고 위쪽으로 이동하는 횟수는 왼쪽보다 한번 줄어드는 것을 알 수 있다. 즉 아래나 
위로 이동할 때마다 횟수가 한 번씩 줄어드는 것이다.

그러면 다음과 같이 채우는 작업을 설계할 수 있다.

 이동횟수 = n
 수 = 1
 행 = 1, 열 = 0

 n이 0보다 큰동안 반복
     이동횟수 만큼 열 증가하고 채우기
     이동횟수 감소
     이동횟수 만큼 행 증가하고 채우기
     이동횟수 만큼 열 감소하고 채우기
     이동횟수 감소
     이동횟수 만큼 행 감소하고 채우기
01 void fill() 
02 { 
03   int i; 
04   int num = 1; 
05   int m = n;        // m은 이동횟수, 처음에는 오른쪽으로 n번 이동해야 한다. 
06   int x = 1, y = 0; // 출발지는 (1, 0)이다. 
07                     // 처음에 오른쪽으로 이동해야 하므로 y = 0이다. 
08   while (m > 0) {   // 이동횟수가 1번 이상인 동안 반복한다. 
09     for (i = 1; i <= m; i++){ // 오른쪽으로 m번 이동하면서 배열을 채운다. 
10       y++; 
11       arr[x][y] = num++; 
12     } 
13 
14     m--; // 아래쪽으로 이동하는 횟수는 오른쪽보다 한번 줄어든다. 
15     for (i = 1; i < = m; i++){ // 아래쪽으로 m번 이동하면서 배열을 채운다. 
16       x++; 
17       arr[x][y] = num++; 
18     } 
19 
20     for (i = 1; i <= m; i++){ // 왼쪽으로 m번 이동하면서 배열을 채운다. 
21       y--; 
22       arr[x][y] = num++; 
23     } 
24 
25     m--; // 윗쪽으로 이동하는 횟수는 왼쪽보다 한번 줄어든다. 
26     for (i = 1; i <= m; i++){ // 윗쪽으로 m번 이동하면서 배열을 채운다. 
27       x--; 
28       arr[x][y] = num++; 
29     } 
30   } 
31 } 


<생각하기>
또 다른 방법을 생각해 보자.
매번 이동하는 횟수를 계산하는 게 귀찮다면 그냥 진행 방향으로 이동을 하다가 벽을 만나면 방향을 바꾸는 방법으로 프로그래밍 할 수 있다.
배열 전체를 0으로 초기화 한 후 출력할 영역 바깥 부분을 모두 1로 채워서 테두리를 만든다. 그리고 진행방향으로 이동을 하면서 채워나가다가 다음에 
이동할 위치에 채울 수 없다면(0이 아니라면) 이동을 멈추고 방향을 바꾼다.


아래의 프로그램을 보면서 잘 생각해 보면 어렵지 않게 작성할 수 있다. 
 이런 방법을 잘 알아두면 수식으로 처리하기 복잡한 문제에서 매우 유용하게 활용할 수 있다.
01 void fill() 
02 { 
03   int i; 
04   int x = 1, y = 0, num = 1; 
05 
06   for (i = 0; i <= n + 1; i++) { 
07     arr[0][i] = arr[n+1][i] = 1; // 0행(맨위), n+1행(맨아래) 모두 1로 채우기 
08     arr[i][0] = arr[i][n+1] = 1; // 0열(맨앞), n+1열(맨뒤) 모두 1로 채우기 
09   } 
10 
11   while (num <= n*n) { // 채울 수가 n*n 이하인 동안 
12     while(arr[x][y+1]==0){ // 오른쪽이 0인동안 
13       y++;                 // 오른쪽으로 이동 
14       arr[x][y]=num++; 
15     } 
16     while(arr[x+1][y]==0){ // 아래쪽이 0인동안 
17       x++;                 // 아래쪽으로 이동 
18       arr[x][y]=num++; 
19     } 
20     while(arr[x][y-1]==0){ // 왼쪽이 0인동안 
21       y--;                 // 왼쪽으로 이동 
22       arr[x][y]=num++; 
23     } 
24     while(arr[x-1][y]==0){ // 위이 0인동안 
25       x--;                 // 위쪽으로 이동 
26       arr[x][y]=num++; 
27     } 
28   } 
29 }



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.