[자료구조] 달팽이 알고리즘 C#

달팽이 알고리즘(Snail Sort 또는 Spiral Order Traversal)은 행렬(matrix)을 처음부터 끝까지 달팽이의 움직임과 유사하게 순회하는 알고리즘입니다. 이 알고리즘은 행렬의 각 원소를 한 번씩만 방문하면서 순회합니다.

알고리즘의 움직임은 아래와 같습니다:

첫 번째 행을 왼쪽에서 오른쪽으로 순회합니다.
마지막 열을 위에서 아래로 순회합니다.
마지막 행을 오른쪽에서 왼쪽으로 순회합니다.
첫 번째 열을 아래에서 위로 순회합니다.
이 과정을 반복하면서 행렬의 중앙까지 진행하게 됩니다. 만약 행과 열의 크기가 홀수인 경우에는 마지막 단계에서 중앙에 위치한 원소가 중복해서 방문되게 됩니다.

다음은 3x3 행렬에 대한 달팽이 알고리즘의 동작 예시입니다:
1 2 3
8 9 4
7 6 5
이 알고리즘은 주로 2차원 배열을 나선형으로 순회해야 할 때 사용됩니다. 구현은 프로그래밍 언어에 따라 다르지만, 주로 중첩된 반복문을 사용하여 각 단계를 처리합니다.

        int[,] board;

        void SetBoard(int size)
        {
            board = new int[size, size];

            int dir = 0;
            int y = 0;
            int x = 0;
            int[] dy = { 0, 1, 0, -1 };
            int[] dx = { 1, 0, -1, 0 };

            int num = 1;
            while (true)
            {
                board[y, x] = num;

                int nextY = y + dy[dir];
                int nextX = x + dx[dir];

                if (num == size * size)
                    break;

                if (CanGo(size, nextY, nextX))
                {
                    y = nextY;
                    x = nextX;
                    num++;
                }
                else
                {
                    dir = (dir + 1) % 4;
                }
            }
        }

        void PrintBoard(int size)
        {
            for (int y = 0; y < size; y++)
            {
                for (int x = 0; x < size; x++)
                {
                    Console.Write(board[y, x].ToString("00") + " ");
                }
                Console.WriteLine();
            }
        }

        bool CanGo(int size, int y, int x)
        {
            if (y < 0 || y >= size)
                return false;

            if (x < 0 || x >= size)
                return false;

            if (board[y, x] != 0)
                return false;

            return true;
        }