페북에 올라온 Zig-zag scan 풀이…

페북에 재미있는 질문이 올라왔다.

아래와 같이 16개의 데이터를 정렬한 뒤 지그재그 형태로 출력하려면 어떻게 해야 되는가가 골자였다.

사실 이 문제는 멀티미디어 쪽 종사자라면 굉장히 자주 접하는 문제^[각주:1]다.

정석적인 풀이는 지그재그 테이블을 생성하고 그 테이블에 따라 값을 출력하는 것이다.

4행부터 시작되는 MakeZigzagTable() 함수가 그 테이블을 생성해주는 함수이다.

#include <stdio.h>
#include <stdlib.h>

int *MakeZigzagTable(int nWidth) {
    int *table = new int[nWidth*nWidth];

    bool directionIsUp = true;
    int x = 0, y = 0;
    int val = 0;

    while (true) {
        table[y*nWidth + x] = val++;
        if ((x == (nWidth - 1)) && (y == (nWidth - 1))) break;
        if (directionIsUp) {
            x++;    y--;
            if (x >= nWidth) {
                x = nWidth - 1;
                y += 2;
                directionIsUp = false;
            }
            else if (y < 0) {
                y = 0;
                directionIsUp = false;
            }
        }
        else {
            x--;    y++;
            if (y >= nWidth) {
                x += 2;
                y = nWidth - 1;
                directionIsUp = true;
            }
            else if (x < 0) {
                x = 0;
                directionIsUp = true;
            }
        }
    }

    return table;
}

int iCompare(const void *arg1, const void *arg2)
{
    return *(int *)arg1 - *(int *)arg2;
}

int main(int argc, char* argv[])
{
    const int nWidth = 4;

    int *data = new int[nWidth*nWidth];
    for (int i = 0; i < nWidth*nWidth; i++) {
        data[i] = rand() % 1000;
    }
    qsort((void*)data, nWidth*nWidth, sizeof(int), iCompare);
    
    int *table = MakeZigzagTable(nWidth);

    for (int y = 0; y < nWidth; y++) {
        for (int x = 0; x < nWidth; x++) {
            printf("%3d ", data[table[y * nWidth + x]]);
        }
        printf("\n");
    }

    delete table;
    delete data;
    return 0;
}

그런데, 사실 실전적인, 최적화된 해법은 저런 테이블을 일일이 돌려서 만드는 게 아니다.

그냥 테이블 하나 만들어놓고 그대로 참조하는 것이다.

애초에 문제에 4x4라고 명시되어 있는데, 굳이 다른 크기의 배열에서도 동작하는 함수를 만들 필요가 없다.

#include <stdio.h>
#include <stdlib.h>

static int zigzag4[] = {
    0,  1,  5,  6,
    2,  4,  7,  12,
    3,  8,  11, 13,
    9,  10, 14, 15
};

int iCompare(const void *arg1, const void *arg2)
{
    return *(int *)arg1 - *(int *)arg2;
}

int main(int argc, char* argv[])
{
    const int nWidth = 4;

    int *data = new int[nWidth*nWidth];
    for (int i = 0; i < nWidth*nWidth; i++) {
        data[i] = rand() % 1000;
    }
    qsort((void*)data, nWidth*nWidth, sizeof(int), iCompare);

    for (int y = 0; y < nWidth; y++) {
        for (int x = 0; x < nWidth; x++) {
            printf("%3d ", data[zigzag4[y * nWidth + x]]);
        }
        printf("\n");
    }

    delete data;
    return 0;
}

게다가, 이 쪽이 코드의 크기도 짧고 이해하기도 쉽다.

덧1. 실행 결과는 물론 동일하다.

 41 145 358 464
169 334 467 724
281 478 705 827
491 500 961 962

덧2. 초등학교 때 컴퓨터 경진대회에서 비슷한 문제를 풀어본 적이 있다.

결국 문제를 풀지 못했는데, 지금 보면 문제의 난이도가 굉장히 높았다.

일단, 문제 자체를 이해할 수가 없었다. (관련 포스트 보기)

1. JPEG/MPEG1 인코딩 시 8x8 블록 단위로 지그재그 코딩을 함 [본문으로]