[C][2차원배열]달팽이 배열

달팽이 배

달팽이 배열은 2차원 배열에 숫자를 소용돌이 모양으로 초기화하는 배열입니다.

모습은 다음과 같습니다.

<그림 출처 : http://www.softqt.com/softqt/board.php?board=research2&command=body&no=34>

 

n x n 배열에서 규칙을 찾아보면

첫 인덱스부터 가로 n, 세로 n-1, 가로 n-1, 세로 n-2 순으로 돌아가는 것을 알 수 있습니다.

즉, 5 x 5 배열에서 보면 5 4 4 3 3 2 2 1 1 순으로 가로와 세로를 번갈아가며 초기화하는 것을 볼 수 있습니다.

그리고 가로와 세로가 세트로 돌아올 때마다 index의 변화가 양수 -> 음수, 음수 -> 양수로 변하는 것도 볼 수 있습니다.

 

이를 통해 먼저 5 4 4 3 3 2 2 1 1 순으로 반복하는 규칙과 가로와 세로를 한 세트로 하되 index의 변화가 양수 -> 음수, 음수 -> 양수로 변화하는 규칙 두 가지를 가지면 됩니다.

 

<5 x 5 달팽이 배열 코드>

int arData[5][5] = {};
int nX = 0;
int nY = 0;
int nCount = 0;
int nMaxCount = 0;
int nData = 0;
int nAdd = 0;
int nFlag = 0;

nData = 1;
nCount = 5;
nMaxCount = (nCount * 2) - 1;
nAdd = 1;
nX = -1;
for (int i = 0; i < nMaxCount; i++) {
	nCount -= i % 2;
	for (int j = 0; j < nCount; j++) {
		if (nFlag == 0) {
			nX += nAdd;
		}
		else {
			nY += nAdd;
		}
		arData[nY][nX] = nData++;
	}
	nFlag++;

	if (nFlag == 2) {
		nFlag = 0;
		nAdd *= -1;
	}
}

for (int i = 0; i < 5; i++) {
	for (int j = 0; j < 5; j++) {
		printf("%2d ", arData[i][j]);
	}
	printf("\n");
}

nCount변수에 (i % 2)의 값을 빼는 것을 통해 5 4 4 3 3 2 2 1 1 순으로 반복이 될 수 있도록 하였습니다.

(규칙을 설정할 때 나머지 연산을 많이 사용한다.)

nFlag라는 변수를 통해 행과 열의 index이동을 구분하고 nFlag의 값이 2가 되는 순간 nFlag의 값을 다시 0으로 초기화하고 nAdd의 값에 -1을 곱하여 index의 변화를 표현하였습니다.

 

위의 코드에서 nCount변수를 int형으로 선언하였기 때문에 나머지 연산을 사용하였지만 nCount를 float형으로 선언한다면 매번 0.5씩 값을 빼주는 방식을 사용한다면 좀 더 간단하게 표현할 수 있습니다.

 

위의 방식이 아닌 동적 프로그래밍 방식을 통해 풀 수 있습니다.

동적 프로그래밍은 배열에 조건을 담아서 꺼내쓰는 방식을 사용하여 조건문을 제거합니다. 

 

이를 위해서는 달팽이 배열에서 조건을 찾아야 합니다.

달팽이 배열에서 조건문이 발생하는 곳은 배열의 index연산을 해야 하기 때문입니다. 

이 조건은 배열에 담아서 사용합니다. 

 

index의 조건은 열 index +1, 행 index +1, 열 index -1, 행 index -1 가 반복하는 조건입니다.

이를 배열로 표현한다면 다음 그림과 같습니다.

 

nY는 행의 index를 nX는 열의 index를 의미합니다.

이것을 조건으로 하여 코드에서 활용합니다.

 

<전체코드>

int arData[5][5] = {};
int arAdd[4][2] = { {0, 1}, {1, 0}, {0, -1}, {-1, 0} };
int nX = 0;
int nY = 0;
int nCount = 0;
int nMaxCount = 0;
int nRest = 0;
int nData = 0;

nData = 1;
nX = -1;
nCount = 5;
nMaxCount = (nCount * 2) - 1;
nRest = 4;
for (int i = 0; i < nMaxCount; i++) {
	nRest = i % 4;
	nCount -= i % 2;
	for (int j = 0; j < nCount; j++) {
		arData[nY += arAdd[nRest][0]][nX += arAdd[nRest][1]] = nData++;
	}
}

for (int i = 0; i < 5; i++) {
	for (int j = 0; j < 5; j++) {
		printf("%2d ", arData[i][j]);
	}
	printf("\n");
}