N Log

2차원 배열을 달팽이 모양으로 배우기

문제

 1  2  3  4  5
16 17 18 19  6
15 24 25 20  7
14 23 22 21  8
13 12 11 10  9

풀이

사각형 범위를 줄이면서 채우는 방법

#include <stdio.h>

int main(void)
{
    enum { SIZE = 5 };

    int arr[SIZE][SIZE] = { 0 };

    int top = 0;
    int bottom = SIZE - 1;
    int left = 0;
    int right = SIZE - 1;

    int count = 1;

    while (left <= right)
    {
        for (int col = left; col <= right; col++)
        {
            arr[top][col] = count++;
        }

        top++;

        for (int row = top; row <= bottom; row++)
        {
            arr[row][right] = count++;
        }

        right--;

        for (int col = right; col >= left; col--)
        {
            arr[bottom][col] = count++;
        }

        bottom--;

        for (int row = bottom; row >= top; row--)
        {
            arr[row][left] = count++;
        }

        left++;
    }

    for (int i = 0; i < SIZE; i++)
    {
        for (int j = 0; j < SIZE; j++)
        {
            printf("%2d ", arr[i][j]);
        }

        printf("\n");
    }

    return 0;
}

spiral matrix boundary overview spiral matrix boundary segments

사각형이 4개의 변으로 이루어져 있듯이, 이 코드는 배열의 테두리를 4개의 구간인 top row, right col, bottom row, left col로 나누어 채운다.
이 순서로 한 바퀴를 채운 뒤 안쪽으로 범위를 좁혀 다시 채우는 과정을 반복하면 전체 달팽이 모양이 완성된다.

1회차: 첫 번째 테두리

  • top row: (0, 0)부터 (0, 4)까지 5회 반복하며 1, 2, 3, 4, 5를 채운다.
    다음 right col은 (1, 4)에서 시작해야 하고, 2회차의 top row는 (1, 1)부터 시작해야 하므로 top을 증가시켜 top은 0에서 1이 된다.

  • right col: (1, 4)부터 (4, 4)까지 4회 반복하며 6, 7, 8, 9를 채운다.
    다음 bottom row는 (4, 3)에서 시작해야 하고, 2회차의 right col은 (2, 3)부터 시작해야 하므로 right를 감소시켜 right는 4에서 3이 된다.

  • bottom row: (4, 3)부터 (4, 0)까지 4회 반복하며 거꾸로 10, 11, 12, 13을 채운다.
    다음 left col은 (3, 0)에서 시작해야 하고, 2회차의 bottom row는 (3, 2)부터 시작해야 하므로 bottom을 감소시켜 bottom은 4에서 3이 된다.

  • left col: (3, 0)부터 (1, 0)까지 3회 반복하며 거꾸로 14, 15, 16을 채운다.
    다음 top row는 (1, 1)에서 시작해야 하고, 2회차의 left col은 (2, 1)부터 시작해야 하므로 left를 증가시켜 left는 0에서 1이 된다.

  • 마무리: 여기까지 하면 바깥 테두리 한 바퀴가 끝난다.
    다음에 채울 범위는 top 1, right 3, bottom 3, left 1이다.

2회차: 두 번째 테두리

  • top row: (1, 1)부터 (1, 3)까지 3회 반복하며 17, 18, 19를 채운다.
    다음 right col은 (2, 3)에서 시작해야 하고, 3회차의 top row는 (2, 2)부터 시작해야 하므로 top을 증가시켜 top은 1에서 2가 된다.

  • right col: (2, 3)부터 (3, 3)까지 2회 반복하며 20, 21을 채운다.
    다음 bottom row는 (3, 2)에서 시작해야 하므로, right를 감소시켜 right는 3에서 2가 된다.

  • bottom row: (3, 2)부터 (3, 1)까지 2회 반복하며 거꾸로 22, 23을 채운다.
    다음 left col은 (2, 1)에서 시작해야 하므로 bottom을 감소시켜 bottom은 3에서 2가 된다.

  • left col: (2, 1)부터 (2, 1)까지 1회 반복하며 24를 채운다.
    다음 top row는 (2, 2)에서 시작해야 하므로 left를 증가시켜 left는 1에서 2가 된다.

  • 마무리: 여기까지 하면 두 번째 테두리도 끝난다.
    다음에 채울 범위는 top 2, right 2, bottom 2, left 2이다.

3회차: 가운데 한 칸

  • top row: (2, 2)부터 (2, 2)까지 1회 반복하며 25를 채운다.
    이 한 칸을 채운 뒤 top을 증가시켜 top은 2에서 3이 된다.

  • 나머지 구간: 각 for 문은 조건식을 만족하지 않아 실행되지 않는다.
    인덱스 상태는 top 3, bottom 1, right 1, left 3이 된다.
    그래서 위쪽 경계가 아래쪽 경계를 지나고, 오른쪽 경계가 왼쪽 경계를 지나 서로 교차한 상태가 된다.

  • 마무리: 이제 left가 3이고 right가 1이라서 while (left <= right) 조건이 거짓이 된다.
    그래서 반복이 끝나고 달팽이 배열이 완성된다.

다음 칸을 확인하며 방향을 바꾸는 방법

#include <stdio.h>

int main(void)
{
    enum { SIZE = 5 };

    int arr[SIZE][SIZE] = { 0 };
    int row = 0;
    int col = 0;
    int direction = 0;
    int row_delta[4] = { 0, 1, 0, -1 };
    int col_delta[4] = { 1, 0, -1, 0 };

    for (int num = 1; num <= SIZE * SIZE; num++)
    {
        arr[row][col] = num;

        int next_row = row + row_delta[direction];
        int next_col = col + col_delta[direction];

        if (next_row < 0 || next_row >= SIZE ||
            next_col < 0 || next_col >= SIZE ||
            arr[next_row][next_col] != 0)
        {
            direction = (direction + 1) % 4;
        }

        row += row_delta[direction];
        col += col_delta[direction];
    }

    for (int i = 0; i < SIZE; i++)
    {
        for (int j = 0; j < SIZE; j++)
        {
            printf("%2d ", arr[i][j]);
        }

        putchar('\n');
    }

    return 0;
}

달팽이 배열의 이동 방향은 오른쪽, 아래, 왼쪽, 위 순서로 반복된다.
이 네 방향에서 행과 열이 어떻게 변하는지를 row_delta와 col_delta 배열에 담아 둔다.

int row_delta[4] = { 0, 1, 0, -1 };
int col_delta[4] = { 1, 0, -1, 0 };

두 배열에서 같은 인덱스에 있는 값을 활용하면 다음에 어느 칸으로 이동해야 하는지 계산할 수 있다.

  • 인덱스 0은 왼쪽 → 오른쪽 방향이며, 행은 그대로 두고 열만 1씩 증가시킨다.
  • 인덱스 1은 위 → 아래 방향이며, 열은 그대로 두고 행만 1씩 증가시킨다.
  • 인덱스 2는 오른쪽 → 왼쪽 방향이며, 행은 그대로 두고 열만 1씩 감소시킨다.
  • 인덱스 3은 아래 → 위 방향이며, 열은 그대로 두고 행만 1씩 감소시킨다.

핵심은 이동 규칙을 찾는 것뿐만 아니라, 언제 방향을 바꿔야 하는지를 코드로 표현하는 데 있다.
row와 col 자체를 바꿔서 다음 칸이 유효한지 확인하면, 두 변수는 현재 위치를 가리키는 역할과 다음 위치를 검사하는 역할을 동시에 맡게 된다.
그러면 다음 칸이 유효하지 않을 때 원래 위치로 되돌리는 처리가 필요해지고, 코드 흐름도 복잡해진다.
그래서 next_row와 next_col 변수로 다음 칸을 미리 계산하고, 그 위치가 배열 범위를 벗어나거나 이미 채워진 칸이면 방향을 바꾼다.
이렇게 방향을 먼저 확정한 뒤 row와 col을 갱신하면, 두 변수는 항상 실제로 값을 넣을 수 있는 유효한 위치만 가리키게 된다.

사각형 범위를 줄이면서 채우는 방법 - 재귀 함수

이전 코드를 살펴보면 현재 사각형의 테두리를 채운 뒤, 범위를 한 칸씩 줄여 더 작은 사각형에 같은 과정을 반복하고 있다.
재귀 함수는 바로 이런 구조처럼 같은 논리를 더 작은 문제에 반복해서 적용하는 방식이므로, 앞의 코드를 재귀 함수로 구현할 수 있다.

#include <stdio.h>

enum { SIZE = 5 };

void fill_spiral_matrix_recursive(int arr[][SIZE], int top, int bottom, int left, int right, int *count)
{
    if (left > right)
    {
        return;
    }

    for (int col = left; col <= right; col++)
    {
        arr[top][col] = (*count)++;
    }

    top++;

    for (int row = top; row <= bottom; row++)
    {
        arr[row][right] = (*count)++;
    }

    right--;

    for (int col = right; col >= left; col--)
    {
        arr[bottom][col] = (*count)++;
    }

    bottom--;

    for (int row = bottom; row >= top; row--)
    {
        arr[row][left] = (*count)++;
    }

    left++;

    fill_spiral_matrix_recursive(arr, top, bottom, left, right, count);
}

int main(void)
{
    int arr[SIZE][SIZE] = { 0 };
    int count = 1;

    fill_spiral_matrix_recursive(arr, 0, SIZE - 1, 0, SIZE - 1, &count);

    for (int i = 0; i < SIZE; i++)
    {
        for (int j = 0; j < SIZE; j++)
        {
            printf("%2d ", arr[i][j]);
        }

        putchar('\n');
    }

    return 0;
}

두 변을 한 for 문에 묶어서 채우는 방법

#include <stdio.h>

int main(void)
{
    enum { SIZE = 5 };

    int arr[SIZE][SIZE] = { 0 };

    int row = 0;
    int col = -1;
    int direction = 1;

    int row_count = SIZE;
    int counter = 0;

    while (counter < SIZE * SIZE)
    {
        int fill_count = 2 * row_count - 1;

        for (int i = 0; i < fill_count; i++)
        {
            if (i < row_count)
            {
                col += direction;
            }
            else
            {
                row += direction;
            }

            arr[row][col] = ++counter;
        }

        direction *= -1;
        row_count--;
    }

    for (int i = 0; i < SIZE; i++)
    {
        for (int j = 0; j < SIZE; j++)
        {
            printf("%2d ", arr[i][j]);
        }

        printf("\n");
    }

    return 0;
}

spiral matrix boundary pair groups 5x5

앞의 사각형 범위 풀이는 한 회차 안에서 위쪽 행, 오른쪽 열, 아래쪽 행, 왼쪽 열의 4개 구간으로 나누어 사각형을 채웠다.
이번 풀이는 마지막 한 칸만 채우는 회차를 제외하면, 한 회차에서 행 채우기 한 번과 열 채우기 한 번을 처리한다.
즉 한 회차에서 사각형 테두리의 대략 절반에 해당하는 두 구간을 채운다.

5x5 배열에서는 회차가 진행될수록 채우는 횟수와 이동 방향이 다음처럼 바뀐다.

  • 1회차: 열이 증가하는 방향으로 행 채우기 5번과 행이 증가하는 방향으로 열 채우기 4번을 수행한다.
  • 2회차: 열이 감소하는 방향으로 행 채우기 4번과 행이 감소하는 방향으로 열 채우기 3번을 수행한다.
  • 3회차: 열이 증가하는 방향으로 행 채우기 3번과 행이 증가하는 방향으로 열 채우기 2번을 수행한다.
  • 4회차: 열이 감소하는 방향으로 행 채우기 2번과 행이 감소하는 방향으로 열 채우기 1번을 수행한다.
  • 5회차: 열이 증가하는 방향으로 행 채우기 1번만 수행한다.

각 회차에서 행 방향으로 채워야 하는 칸 수를 row_count로 잡았다.
그러면 열 방향으로 채워야 하는 칸 수는 항상 row_count - 1이므로,
이번 회차에서 채울 전체 칸 수는 row_count + row_count - 1 또는 2 * row_count - 1로 구할 수 있다.

행과 열을 한 회차에서 함께 처리하더라도, 역시 중요한 것은 회전을 코드로 구현하는 부분이다.
그림을 보면 회전이 되는 경우는 한 행의 칸 수를 다 처리했을 때이다.
따라서 if (i < row_count) 코드로 행을 다 처리했는지 검사한다.

앞에서는 행을 채울 차례인지 열을 채울 차례인지 구분했다.
실제로 행이나 열을 채울 때는 += direction을 이용한다.
위의 규칙에서 홀수 회차는 증가하는 방향이고, 짝수 회차는 감소하는 방향인 것을 알 수 있기 때문이다.
한 회차가 끝나면 direction *= -1로 이동 방향을 반대로 바꾼다.
또한, 다음 회차에서 채워야 하는 행 개수가 감소하니 row_count--를 해준다.