[알고리즘] : L-tailing(트로미노)(C)

이번 시간에는 L-tailing 알고리즘을 풀어 볼 예정이다.

[문제]

L-형 타일로 덮을 수 있는지 아닌지를 판별하고, 가능하면 실제 패킹을 출력하는 프로그램을 작성하시오.

[입력]

[출력]

<코드>

#include <stdio.h>
#include <math.h>


int a_xy[1000][1000];
int num = 1;



void tromino(int x, int y, int size_q, int x_row, int y_col)
{
    int middle_x, middle_y, i;
    middle_x = x + size_q / 2; //middle x변수 타일 기준으로 정확히 반을 나누는 기준점이된다. (행령이라고 생각하면 쉬움)
    middle_y = y + size_q / 2; //위와 같이 middle_y변수 


    int total_x[4] = { middle_x, middle_x - 1, middle_x - 1, middle_x }; //각 변수의 사분면을 total_x에 담아준다. (해당 좌표가 갖고 있는 의미를 알고 있는 것이 중요하다.)
    int total_y[4] = { middle_y - 1, middle_y - 1, middle_y, middle_y }; // if) middle_x & middle_y가 될 수 있고 배열에 저장되어 있는 변수로 경우의 수를 나눌 예정이다.


    if (x_row >= middle_x && y_col < middle_y) //만약에 x_row가 더 크고, y가 작은 조건을 만들고 그것이 -> 1사분면을 의미한다. 
        total_x[0] = x_row, total_y[0] = y_col; // 값을 저장하기 위해 x_row와 y_col값을 저장한다. 이후에 출력할 떄 사용된다.
    else if (x_row < middle_x && y_col < middle_y) // 2사분면을 의미한다. 
        total_x[1] = x_row, total_y[1] = y_col;
    else if (x_row < middle_x && y_col >= middle_y) // 3사분면 
        total_x[2] = x_row, total_y[2] = y_col;
    else
        total_x[3] = x_row, total_y[3] = y_col; //4사분면 

    show_tromino( total_x,  total_y,  x_row,  y_col,  num);

    num++;

    if (size_q > 2) //재귀를 통해서 나눠준다.
    {
        tromino(middle_x, y, size_q / 2, total_x[0], total_y[0]); 
        tromino(x, y, size_q / 2, total_x[1], total_y[1]);
        tromino(x, middle_y, size_q / 2, total_x[2], total_y[2]);
        tromino(middle_x, middle_y, size_q / 2, total_x[3], total_y[3]);
    }
}



int show_tromino(int * total_x, int * total_y, int x_row, int y_col, int num)  // total_x / total_y에 저장되어 있는 값과 num를 return 하는 함수다.
{
    int i;
    for (i = 0; i < 4; i++)
    {
        if (total_x[i] == x_row && total_y[i] == y_col) continue; //저장되어 있는 값과 x_row가 같은 경우 / y도 동일하게 진행한다.
        a_xy[total_y[i]][total_x[i]] = num;
    }
   
    return num;
}

int main()
{
    int size_q, n, x, y, i, j;
    scanf_s("%d%d%d", &n, &y, &x); // 사용자로부터 값을 받는다.
    size_q = pow(2, n); // pow함수를 통해서 2^k승을 표현했다.
    y--, x--;
    a_xy[y][x] = -1;
    tromino(0, 0, size_q, x, y);
    for (i = 0; i < size_q; i++) //size_q(크기) 만큼 돌면서 값을 출력한다.
    {
        for (j = 0; j < size_q; j++)
        {
            if (i == y && j == x) //만약에 x,y좌표와 인덱스 i,j값이 같다면 0을 출력한다.
                printf("0 ");
            else
                printf("%d ", a_xy[i][j]);
        }
        printf("\n");
    }
}

<결과>