[C++] BOJ 18808번: 스티커 붙이기

문제 링크

문제 풀이

문제에 주어진 조건을 시뮬레이션하기 위해 스티커가 주어졌을 때, n번째 스티커의 회전 상태의 따른 세로 길이를 저장하는 배열 R과 C를 만들어 주었다. '한 번도 회전하지 않은 상태의 n번째 스티커의 가로와 세로 길이'를 이용하여 R과 C를 계산하는 함수를 만들고, '한 번도 회전하지 않은 상태의 n번째 스티커의 가로와 세로 길이'가 주어지면 앞에서 만든 함수를 실행해 주었다.

 

코드는 아래에 적은 과정을 반복하여 상황을 시뮬레이션 한다.

1. 노트북에 현재 회전 상태의 n번째 스티커를 붙일 수 있는 위치가 있는지 확인

2. n번째 스티커를 붙일 수 있는 위치가 있으면 해당 스티커에 대한 반복을 종료. 위치가 없으면 n번째 스티커를 90도 회전 시킴

3. 위의 1, 2 과정을 반복하고 n번째 스티커를 270도 회전 시켜도 붙일 수 없음을 확인하면 다음 n+1번째 스티커에 대해서 반복

 

마지막에는 노트북의 1의 갯수를 세어 결과를 출력한다.

코드

#include <iostream>
#include <vector>

using namespace std;

int N, M, K;                  // N - 세로, M - 가로, K - 모눈 종이 수
int R[103][4];                // R[n번째][회전] - 세로
int C[103][4];                // C[n번째][회전] - 가로
bool sticker[20][20][103][4]; // sticker[세로][가로][n번째][회전]
bool notebook[50][50];        // notebook[세로][가로]

void printNotebook()
{
    cout << "-------------------------------" << '\n';
    for (int p = 0; p < N; p++)
    {
        for (int q = 0; q < M; q++)
        {
            cout << notebook[p][q] << ' ';
        }
        cout << '\n';
    }
    cout << "-------------------------------" << '\n';
}

void calcRotatedSticker(int nth)
{
    int width = C[nth][0];
    int height = R[nth][0];

    R[nth][1] = R[nth][3] = width;
    C[nth][1] = C[nth][3] = height;

    R[nth][2] = height;
    C[nth][2] = width;

    for (int degree = 0; degree < 3; degree++)
    {
        for (int i = 0; i < R[nth][degree]; i++) // i가 세로
        {
            for (int j = 0; j < C[nth][degree]; j++) // j가 가로
            {
                sticker[j][R[nth][degree] - 1 - i][nth][(degree + 1) % 4] = sticker[i][j][nth][degree];
            }
        }
    }
}

bool checkAttachable(int startY, int startX, int nth, int degree)
{
    int width, height;
    height = R[nth][degree];
    width = C[nth][degree];

    if (height > N || width > M)
        return false;

    for (int i = 0; i < height; i++)
    {
        for (int j = 0; j < width; j++)
        {
            if (notebook[startY + i][startX + j] && sticker[i][j][nth][degree])
                return false;
        }
    }

    return true;
}

void attachSticker(int startY, int startX, int nth, int degree)
{
    int width, height;
    height = R[nth][degree];
    width = C[nth][degree];

    for (int i = 0; i < height; i++)
    {
        for (int j = 0; j < width; j++)
        {
            if (sticker[i][j][nth][degree] == 1)
                notebook[startY + i][startX + j] = sticker[i][j][nth][degree];
        }
    }

    // printNotebook();
}

int main(void)
{
    cin.tie(nullptr);
    ios::sync_with_stdio(false);

    cin >> N >> M >> K;

    int input;

    for (int i = 0; i < K; i++)
    {
        cin >> R[i][0] >> C[i][0];

        int width = C[i][0];
        int height = R[i][0];

        for (int p = 0; p < height; p++)
        {
            for (int q = 0; q < width; q++)
            {
                cin >> input;
                sticker[p][q][i][0] = (input == 1);
            }
        }

        calcRotatedSticker(i);

        bool attachFlag = false;
        for (int degree = 0; degree < 4; degree++)
        {
            width = C[i][degree];
            height = R[i][degree];
            for (int p = 0; p <= (N - height); p++)
            {
                for (int q = 0; q <= (M - width); q++)
                {
                    if (checkAttachable(p, q, i, degree))
                    {
                        attachFlag = true;
                        attachSticker(p, q, i, degree);
                    }
                    if (attachFlag)
                        break;
                }
                if (attachFlag)
                    break;
            }
            if (attachFlag)
                break;
        }
    }

    int result = 0;

    for (int p = 0; p < N; p++)
    {
        for (int q = 0; q < M; q++)
        {
            if (notebook[p][q])
                result++;
        }
    }

    cout << result << '\n';

    return 0;
}