[BOJ] C++ 18808: 스티커 붙이기 - 시뮬레이션

18808번: 스티커 붙이기

예제가 굉장히 많아서 백준에서 보시는 것을 추천합니다.

---

문제를 요약해 보면서 어떤 기능을 구현해야 할지 생각해 보자.

1. 스티커를 다른 스티커와 겹치지 않게 가장 위쪽 중 왼쪽에 붙인다.
2. 붙일 수 없다면 90, 180, 270도 회전해서 붙여 본다.
3. 그래도 붙일 수 없다면 그 스티커는 버린다.

여기까지 봤을 때 구현사항은 세 가지 정도 보인다.

1. 스티커 붙이기
2. 스티커 회전하기
3. 답 계산하기

스티커를 붙이는 게 가장 중요해 보이는데, 여기서 시간 복잡도가 결정될 것 같다. 가장 먼저 생각난 풀이는 모든 칸에 붙이려는 스티커 (0, 0)을 붙여보고 안되면 회전시키는 방식이다. 먼저 시간을 계산해 보고 괜찮을지 판단했다.

최대 1600개의 모든 칸에 대해 스티커 100개를 붙여봐야 하고, 붙는지 판단하려면 또 스티커의 모든 칸을 판단해야 하므로 1600 * 100 * 100이다. 여기서 모든 스티커를 회전해야 하므로 1600 * 100 * 100 * 4 = 64000000이다. 무조건 2초 안에 구현이 될 것 같으므로 한 번 구현해 보자.

 

• 스티커 붙이기
  그렇게 헷갈리는 부분은 없다. 그냥 붙여보면 된다.

bool paste(int x, int y)
{
    // labtop(x, y)에 현재 스티커(0, 0)을 붙일 수 있는지 체크
    for (int i = 0; i < r; i++)
        for (int j = 0; j < c; j++)
            if (sticker[i][j] == 1 && labtop[x + i][y + j] == 1)
                return false;

    // 붙일 수 있다고 판단. 바로 붙이기
    for (int i = 0; i < r; i++)
        for (int j = 0; j < c; j++)
            if (sticker[i][j] == 1)
                labtop[x + i][y + j] = 1;

    return true;
}

 

• 스티커 회전하기
  이 부분이 구현이 조금 헷갈렸는데, 아직 2차원 배열의 회전이 익숙하지 않다면 이 글을 읽어보자.

[문제풀이] 2차원 배열 90도 회전, 뒤집기 꿀팁

이대로 구현해 주면 되는데, 배열을 회전시키면 행과 열의 크기가 바뀌므로 그 부분만 주의해 주면 된다.

void rotate()
{
    int tmp[12][12];

    for (int i = 0; i < r; i++)
        for (int j = 0; j < c; j++)
            tmp[i][j] = sticker[i][j];

    int tmp_r = r;
    r = c;
    c = tmp_r;

    for (int i = 0; i < r; i++)
        for (int j = 0; j < c; j++)
            sticker[i][j] = tmp[c - 1 - j][i];
}

 

이 함수들을 합쳐서 계산해 주면 되는데, 하나 주의할 점은 paste() 함수를 돌릴 때 0행부터 n-r행까지만 체크해 주면 된다는 것이다. n-r+1행부터는 당연히 스티커를 붙일 수 없다.

/** 시뮬레이션 18808 스티커 붙이기 **/
#include <iostream>
#include <vector>
#include <algorithm>
#include <string>
using namespace std;
int n, m, k;
int labtop[50][50];
int r, c;
int sticker[12][12];

void rotate()
{
    int tmp[12][12];

    for (int i = 0; i < r; i++)
        for (int j = 0; j < c; j++)
            tmp[i][j] = sticker[i][j];

    int tmp_r = r;
    r = c;
    c = tmp_r;

    for (int i = 0; i < r; i++)
        for (int j = 0; j < c; j++)
            sticker[i][j] = tmp[c - 1 - j][i];
}

bool paste(int x, int y)
{
    // labtop(x, y)에 현재 스티커(0, 0)을 붙일 수 있는지 체크
    for (int i = 0; i < r; i++)
        for (int j = 0; j < c; j++)
            if (sticker[i][j] == 1 && labtop[x + i][y + j] == 1)
                return false;

    // 붙일 수 있다고 판단. 바로 붙이기
    for (int i = 0; i < r; i++)
        for (int j = 0; j < c; j++)
            if (sticker[i][j] == 1)
                labtop[x + i][y + j] = 1;

    return true;
}

int main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);

    cin >> n >> m >> k;
    while (k--)
    {
        cin >> r >> c;
        for (int i = 0; i < r; i++)
            for (int j = 0; j < c; j++)
                cin >> sticker[i][j];

        for (int dir = 0; dir < 4; dir++)
        {
            bool flag = false;
            // 붙일 수 있는 칸에 붙여보기. 못붙인다면 방향 회전
            for (int i = 0; i <= n - r; i++)
            {
                if (flag)
                    break;
                for (int j = 0; j <= m - c; j++)
                {
                    if (paste(i, j))
                    {
                        flag = true;
                        break;
                    }
                }
            }
            if (flag)
                break;
            rotate();
        }
    }
    int cnt = 0;
    for (int i = 0; i < n; i++)
        for (int j = 0; j < m; j++)
            if (labtop[i][j])
                cnt++;
    cout << cnt << '\n';
}