정올 C - 1707번 도형만들기2 - 달팽이사각형

728x90

문제 : http://www.jungol.co.kr/bbs/board.php?bo_table=pbank&wr_id=980&sca=2020

JUNGOL

www.jungol.co.kr

문제

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

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

Hint!

<생각하기>

처음에는 (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보다 큰동안 반복

이동횟수 만큼 열 증가하고 채우기

이동횟수 감소

이동횟수 만큼 행 증가하고 채우기

이동횟수 만큼 열 감소하고 채우기

이동횟수 감소

이동횟수 만큼 행 감소하고 채우기

void fill() {

int i;

int num = 1;

int m = n; // m은 이동횟수, 처음에는 오른쪽으로 n번 이동해야 한다.

int x = 1, y = 0; // 출발지는 (1, 0)이다.

// 처음에 오른쪽으로 이동해야 하므로 y = 0이다.

while (m > 0) { // 이동횟수가 1번 이상인 동안 반복한다.

for (i = 1; i <= m; i++) { // 오른쪽으로 m번 이동하면서 배열을 채운다.

y++;

arr[x][y] = num++;

}

m--; // 아래쪽으로 이동하는 횟수는 오른쪽보다 한번 줄어든다.

for (i = 1; i < = m; i++) { // 아래쪽으로 m번 이동하면서 배열을 채운다.

x++;

arr[x][y] = num++;

}

for (i = 1; i <= m; i++) { // 왼쪽으로 m번 이동하면서 배열을 채운다.

y--;

arr[x][y] = num++;

}

m--; // 윗쪽으로 이동하는 횟수는 왼쪽보다 한번 줄어든다.

for (i = 1; i <= m; i++) { // 윗쪽으로 m번 이동하면서 배열을 채운다.

x--;

arr[x][y] = num++;

}

Colored by Color Scripter

<생각하기>

또 다른 방법을 생각해 보자.

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

아래의 프로그램을 보면서 잘 생각해 보면 어렵지 않게 작성할 수 있다.

이런 방법을 잘 알아두면 수식으로 처리하기 복잡한 문제에서 매우 유용하게 활용할 수 있다.

void fill() {

int i;

int x = 1, y = 0, num = 1;

for (i = 0; i <= n + 1; i++) {

arr[0][i] = arr[n+1][i] = 1; // 0행(맨위), n+1행(맨아래) 모두 1로 채우기

arr[i][0] = arr[i][n+1] = 1; // 0열(맨앞), n+1열(맨뒤) 모두 1로 채우기

}

while (num <= n*n) { // 채울 수가 n*n 이하인 동안

while(arr[x][y+1]==0) { // 오른쪽이 0인동안

y++; // 오른쪽으로 이동

arr[x][y]=num++;

}

while(arr[x+1][y]==0) { // 아래쪽이 0인동안

x++; // 아래쪽으로 이동

arr[x][y]=num++;

}

while(arr[x][y-1]==0) { // 왼쪽이 0인동안

y--; // 왼쪽으로 이동

arr[x][y]=num++;

}

while(arr[x-1][y]==0) { // 위이 0인동안

x--; // 위쪽으로 이동

arr[x][y]=num++;

}

정답 :

# include <stdio.h>

int main()
{
	int n,i,j,x = 1,y =0, num=1;
	int arr[100][100];
	
	scanf("%d",&n);
	
	for(i = 0; i<=n; i++)
	{
		arr[0][i] = arr[n+1][i] = 1;
		arr[i][0] = arr[i][n+1] = 1;
	}
	
	while(num <= n*n)
	{
		while(arr[x][y+1] ==0)
		{
			y++;
			arr[x][y] = num++;
		}
		while(arr[x+1][y] == 0)
		{
			x++;
			arr[x][y] = num++;
		}
		while(arr[x][y-1] ==0)
		{
			y--;
			arr[x][y] = num++;
		}
		while(arr[x-1][y] == 0)
		{
			x--;
			arr[x][y] = num++;
		}
	}
	
	
	for(i = 1; i<=n; i++)
	{
		for(j = 1; j<=n; j++)
		{
			printf("%d ",arr[i][j]);
		}
		printf("\n");
	}
	
	return 0;
}

728x90