달팽이 배열

달팽이 배열은 $n \times n$ 배열에 $1$부터 $n^2$ 까지의 자연수를 달팽이 집 모양으로 채우는 문제이다.다음 그림은 $4 \times 4$ 배열에서의 숫자를 채워 나가는 방향과 결과로 얻어지는 배열을 보여준다.

사용자로부터 배열의 크기를 결정하는 $n$ 을 입력받아 달팽이 배열을 만든 후 출력하는 프로그램을 작성하는 것이 이 문제의 목적이다. 

계속 $4 \times 4$ 배열을 예로 들자면, 행과 열의 index 는 다음과 같이 주어질 것이고, 숫자들이 채워질 때는 규칙성이 있게 채워진다는 것을 알아야 한다. 

	(0, 0) 에서 출발하여 오른쪽으로 숫자들을 4 개 채워간다. 오른쪽으로 채운다는 것은 열의 index 가 하나씩 증가하는 것을 의미한다.
	(0, 3) 에서 방향을 바꾸어 아래쪽으로 숫자들을 3개 채워간다. 아래쪽으로 채운다는 것은 행의 index 가 하나씩 증가하는 것을 의미한다.
	(3, 3)에서 방향을 바꾸어 왼쪽으로 숫자들을 3개 채워간다. 왼쪽으로 채운다는 것은 열의 index 가 하나씩 감소하는 것을 의미한다.
	(3, 0)에서 방향을 바꾸어 위쪽으로 숫자들을 2개 채워간다. 위쪽으로 채운다는 것은 행의 index 가 하나씩 감소하는 것을 의미한다.
	(1, 0)에서 방향을 바꾸어 다시 오른쪽으로 숫자들을 2개 채워간다. 오른쪽으로 채운다는 것은 열의 index 가 하나씩 증가하는 것을 의미한다.
	(1, 2)에서 방향을 바꾸어 다시 아래쪽으로 숫자를 1개 채운다. 아래쪽으로 채운다는 것은  행의 index 가 하나씩 증가하는 것을 의미한다.
	(2, 2)에서 방향을 바꾸어 다시 왼쪽으로 숫자를 1개 채운다.  왼쪽으로 채운다는 것은 열의 index 가 하나씩 감소하는 것을 의미한다.

 

위 내용을 일반적인 $n \times n$ 배열에 적용하면 다음과 같다.

오른쪽으로 $n$ 칸 전진 (열 index 1씩 증가)

아래쪽으로 $n-1$ 칸 전진 (행 index 1씩 증가)

왼쪽으로 $n-1$ 칸 전진 (열 index 1씩 감소)

위쪽으로 $n-2$ 칸 전진 (행 index 1씩 감소)

다시 오른쪽으로 $n-2$ 칸 전진 (열 index 1씩 증가)

다시 아래쪽으로 $n-3$ 칸 전진 (행 index 1씩 증가)

다시 왼쪽으로 $n-3$ 칸 전진 (열 index 1씩 감소)

다시 위쪽으로 $n-4$ 칸 전진 (행 index 1씩 감소)

$\vdots$

요약하면 전진하는 양은 $$ n \to n-1 \to n-1 \to n-2 \to n-2 \to n-3 \to n-3 \to \cdots \to 1 \to 1$$ 로 처음 $n$은 한 번 다음부터는 $n$이 1씩 감소하면서 두 번씩 반복되고, 이것은 전진하는 양이 $0$ 이 되기 전까지 계속 된다.

또한 index 의 증감 상태를 행이나 열에 관계없이 보면 처음 두 번은 1씩 증가, 다음 두번은 1씩 감소, 다시 다음 두 번은 1씩 증가, 다시 다음 두 번은 1씩 감소 하는 규칙성을 보여준다.

위와 같은 규칙성에 따라 C 언어로 코딩을 하면 다음과 같다. 

#include<stdio.h>

// 배열을 프린트 해주는 함수 . 배열의 크기 n과 배열을 인자로 받음
void printarr(int n, int (*arr)[n]) {
	int i, j;
	for (i = 0; i < n; i++) {
		for (j = 0; j < n; j++) {
			printf("%3d ", arr[i][j]);
		}
		printf("\n");
	}
}

// 배열을 만들어 주는 함수. 배열의 크기 n과 배열을 인자로 받음
void makearr(int n, int (*arr)[n]) {
	int value = 1;    // 배열을 채워 나갈 값
	int row = 0, col = -1;    // 행(row), 열(col) 을 나타내는 index
	int inc = 1;    // index 의 증감량을 나타냄. 1 또는 -1 을 가질 수 있음
	int i, j;
	while (n > 0) {
		for (i = 0; i < n; i++) {
			col += inc;    // 열 index 를 inc 만큼 증가시킴. inc가 -1이면 감소
			arr[row][col] = value;
			value++;
		}
		n--;    // 전진하는 양 1 감소
		if (n == 0) break;    // 전진하는 양이 0이 되면 while 루프 빠져나옴
		for (i = 0; i < n; i++) {
			row += inc;    // 행 index 를 inc 만큼 증가시킴. inc 가 -1이면 감소
			arr[row][col] = value;
			value++;
		}
		inc *= -1;    //inc 부호바꿈. 증가가 감소로 혹은 감소가 증가로 바뀌는 효과
	}
}


int main(void) {
	int side;
	printf("Input side length of arr : ");
	scanf("%d", &side);
	int arr[side][side];
	makearr(side, arr);    // 배열을 만드는 함수 호출
	printarr(side, arr);    // 배열을 프린트 해주는 함수 호출
	return 0;
}

결과는 다음과 같다.

Input side length of arr : 20
  1   2   3   4   5   6   7   8   9  10  11  12  13  14  15  16  17  18  19  20
 76  77  78  79  80  81  82  83  84  85  86  87  88  89  90  91  92  93  94  21
 75 144 145 146 147 148 149 150 151 152 153 154 155 156 157 158 159 160  95  22
 74 143 204 205 206 207 208 209 210 211 212 213 214 215 216 217 218 161  96  23
 73 142 203 256 257 258 259 260 261 262 263 264 265 266 267 268 219 162  97  24
 72 141 202 255 300 301 302 303 304 305 306 307 308 309 310 269 220 163  98  25
 71 140 201 254 299 336 337 338 339 340 341 342 343 344 311 270 221 164  99  26
 70 139 200 253 298 335 364 365 366 367 368 369 370 345 312 271 222 165 100  27
 69 138 199 252 297 334 363 384 385 386 387 388 371 346 313 272 223 166 101  28
 68 137 198 251 296 333 362 383 396 397 398 389 372 347 314 273 224 167 102  29
 67 136 197 250 295 332 361 382 395 400 399 390 373 348 315 274 225 168 103  30
 66 135 196 249 294 331 360 381 394 393 392 391 374 349 316 275 226 169 104  31
 65 134 195 248 293 330 359 380 379 378 377 376 375 350 317 276 227 170 105  32
 64 133 194 247 292 329 358 357 356 355 354 353 352 351 318 277 228 171 106  33
 63 132 193 246 291 328 327 326 325 324 323 322 321 320 319 278 229 172 107  34
 62 131 192 245 290 289 288 287 286 285 284 283 282 281 280 279 230 173 108  35
 61 130 191 244 243 242 241 240 239 238 237 236 235 234 233 232 231 174 109  36
 60 129 190 189 188 187 186 185 184 183 182 181 180 179 178 177 176 175 110  37
 59 128 127 126 125 124 123 122 121 120 119 118 117 116 115 114 113 112 111  38
 58  57  56  55  54  53  52  51  50  49  48  47  46  45  44  43  42  41  40  39