[알고리즘]달팽이 알고리즘

 

모 회사에서 등장했던 알고리즘이었었고 정보처리 기사에서 자주 등장한다는 그 알고리즘 이다.

 

말 그대로 달팽이 모양으로 빙빙 돌려가며 데이터를 저장하는 거다.

 

뭐 문제는 이러했다.

 

N x N 크기의 배열에 달팽이 모양으로 데이터를 저장하고 싶다.

저장하고자 하는 데이터는 이와 같다. "HELLOWORLD"

 

예로 10x10 행렬에 채우면 다음과 같다.

H	E	L	L	O	W	O	R	L	D
W	O	R	L	D	H	E	L	L	H
O	L	O	W	O	R	L	D	O	E
L	L	L	O	W	O	R	H	W	L
L	E	L	W	O	R	L	E	O	L
E	H	E	O	D	L	D	L	R	O
H	D	H	L	L	E	H	L	L	W
D	L	D	L	R	O	W	O	D	O
L	R	O	W	O	L	L	E	H	R
R	O	W	O	L	L	E	H	D	L

 

여기서의 포인트는….

맨 처음은 가로크기만큼 n번 채우는 것을 한번만 하고

그 뒤로는

위에서 아래로 n-1회, 우에서 좌로 n-1회

아래에서 위로 n-2회, 좌에서 우로 n-2회

위에서 아래로 n-3, 우에서 좌로 n-3

아래에서 위로 n-4회, 좌에서 우로 n-4회

…..

 

이런 방식으로 진행이 되는데.

처음 맨 윗줄을 제외한 끝까지 이동하는 횟수는 방향이 두 번 바뀔 때 마다 한번씩 1씩 줄어 듦.

그리고 달팽이껍질처럼 모이는 방향이 일정하다는 점

 

그래서 코드를 짜보면.

#include <iostream>   char GetChar() {     char Str[] = "HELLOWORLD";     char returnStr;       static int StrIndex = 0;       if (StrIndex >= sizeof(Str)-1)     {         StrIndex = 0;         returnStr = Str[StrIndex];     }     else     {         returnStr = Str[StrIndex];     }     StrIndex++;     return returnStr; }   int main(void) {     int arrSize = 0;       //가로 또는 세로로 갈 때 얼마만큼 넣어줄 것인지에 대한 최댓값     int Max = 0;     int dir = 1; //진행 방향 (해당 방향으로 더해줄 것임)           int x = -1;        //가로     int y = 0;        //세로       printf("배열 크기 입력 : ");     scanf("%d", &arrSize);     Max = arrSize;       //어차피 2차원 배열도 구조상 보면 1차원 배열이므로.     char *arr = new char[arrSize*arrSize];       while (1)     {         //가로 이동         for (int i = 0; i < Max; i++)         {             x = x + dir;             arr[y*arrSize + x] = GetChar();         }           Max--; //최대 진행 값 감소.           if (Max < 0)         {//총 진행 방향으로 가야 할 값이 0보다 작아질 경우 값을 다 넣은 것.             break;         }           //세로 이동         for (int i = 0; i < Max; i++)         {             y = y + dir;             arr[y*arrSize + x] = GetChar();         }           //방향 전환         dir = -dir;     }       //출력     for (int i = 0; i<arrSize; i++ )     {         for (int j = 0; j < arrSize; j++)         {             printf("%c", arr[i*arrSize + j]);         }         printf("\n");     }       delete[] arr;       return 0; }

 

출력결과