[Etc] 중첩된 달팽이 수열

이 문제는 개인적으로 공부를 위해 풀이한 문제이다.

 

일반적으로 달팽이 수열은, 아래와 같이 숫자가 달팽이 모양으로 증가하는 형태의 수열을 의미한다.

// size = 3
1 2 3
8 9 4
7 6 5

중첩된 달팽이 수열은, 여러 단계(?) 로 중첩된 달팽이 수열을 표현하고자 지은 이름인데 의도를 표현하기 적합한 이름인 지는 모르겠다. 간단하게 설명을 하자면 각 단계 별로 수열의 Size 가 주어지고 수열 안에 중첩된 또다른 수열이 존재하는 방식이다. 이를 위처럼 표현하면 다음과 같을 것 같다.

// size = [3, 2]
 1  2  3 10 11 12 
 8  9  4 17 18 13 
 7  6  5 16 15 14 
28 29 30 19 20 21 
35 36 31 26 27 22 
34 33 32 25 24 23

제일 위에서 size 가 3일 때의 달팽이 수열을 표현했는데, 이러한 달팽이 수열을 내부에 갖는 size 가 2인 달팽이 수열을 표현한 것이다.

 

이를 그림으로 표현하면 다음과 같을 수 있겠다.

중첩 달팽이 수열의 size 는 배열로 주어지고, 그 배열이 [3, 2] 와 같을 때의 모습은 위와 같다. 우선, (2 x 2) 의 크기를 갖는 달팽이 수열이 존재하게 된다. 총 4개의 수열로 구성된 이 달팽이 수열은, 각각이 (3 x 3) 의 크기를 갖는 달팽이 수열이다. 만약 size 가 [3, 2, 2] 와 같이 주어진다면 이 수열이 의미하는 바는 위의 수열 4개로 구성된 또다른 달팽이 수열이 될 것이다.

 

우선 이 문제를 해결하기 위해 기본적으로, 달팽이 수열을 만들 수 있어야 하는데 이는 방향 정보를 갖는 변수 하나를 사용함으로써 수열을 표현할 수 있다. 방향의 순서는 오른쪽, 아래, 왼쪽, 위 방향으로 4 가지 방향이 존재하게 되고 이 순서대로 값을 채워나갈 수 있다면 달팽이 수열을 만들 수 있다.

 

그리고 위와 같이 중첩된 수열을 표현하기 위해 재귀함수를 사용할 수 있는데, 각 단계 별로 전체 수열의 크기가 어떻게 되는 지, 초기 수열에서 현재 표현해야 하는 수열의 위치가 어디인 지 정보를 줌으로써 각 함수 호출 단계에서 현재 표현해야 할 수열의 정보를 알 수 있다.

 

이와 같이 문제를 풀이했을 때 작성한 코드는 다음과 같다.

 

#define pow(X) ((X) * (X))

int dr[4] = {0, 1, 0, -1}, dc[4] = {1, 0, -1, 0};
int N;

void fill(vector<vector<int>>& matrix, int sy, int sx, int ey, int ex, int startNum) {
    int y = sy, x = sx, dir = 0, num = startNum;
    while (true) {
        if (y < sy || y > ey || x < sx || x > ex || matrix[y][x] != 0) {
            break;
        }
        matrix[y][x] = num++;
        int ny = y + dr[dir], nx = x + dc[dir];
        if (ny < sy || ny > ey || nx < sx || nx > ex || matrix[ny][nx] != 0) {
            dir = (dir + 1) % 4;
            ny = y + dr[dir], nx = x + dc[dir];
        }
        y = ny;
        x = nx;
    }
}

void solve(vector<vector<int>>& matrix, vector<int>& lengths, int idx, int sy, int sx, int n, int num) {
    if (idx == 0) {
        fill(matrix, sy, sx, sy + lengths[0] - 1, sx + lengths[0] - 1, num);
        return;
    }
    int length = lengths[idx];
    int offset = n / length;
    vector<vector<bool>> vis(length, vector<bool>(length, false));

    int i = 0, j = 0, dir = 0;
    int y = sy, x = sx;
    int nextNum = num;
    while (true) {
        if (vis[i][j])
            break;
        vis[i][j] = true;

        int ni, nj;
        ni = i + dr[dir];
        nj = j + dc[dir];
        if (ni < 0 || ni >= length || nj < 0 || nj >= length || vis[ni][nj]) {
            dir = (dir + 1) % 4;
            ni = i + dr[dir];
            nj = j + dc[dir];
        }

        solve(matrix, lengths, idx - 1, y, x, offset, nextNum);

        y += dr[dir] * offset;
        x += dc[dir] * offset;
        nextNum += pow(offset);

        i = ni;
        j = nj;
    }
}

vector<vector<int>> solution(vector<int> lengths) {
    N = 1;
    for (auto length : lengths) {
        N *= length;
    }

    vector<vector<int>> matrix(N, vector<int>(N, 0));
    solve(matrix, lengths, lengths.size() - 1, 0, 0, N, 1);
    return matrix;
}