[백준] 18808번 스티커 붙이기

문제: 18808번: 스티커 붙이기

basic-algo-lecture/workbook/0x0D.md at master · encrypted-def/basic-algo-lecture

basic-algo-lecture/workbook/0x0D.md at master · encrypted-def/basic-algo-lecture

 

#include <iostream>
#include <vector>
using namespace std;

int n, m, k, r, c, totalCnt = 0;
vector<vector<int>> board;
vector<vector<int>> sticker;

bool IsPossibleFill(int boardX, int boardY) {
    for (int i = 0; i < r; i++) {
        for (int j = 0; j < c; j++) {
            // 범위를 벗어나면 false
            if ((boardY + i >= n) || (boardX + j >= m)) {
                if (sticker[i][j] == 1) return false;
            }
            // 이미 채워져 있으면 false
            else if (board[boardY + i][boardX + j] == 1 && sticker[i][j] == 1)
                return false;
        }
    }
    // 스티커 부착
    for (int i = 0; i < r; i++) {
        for (int j = 0; j < c; j++) {
            if (sticker[i][j] == 1)
                board[boardY + i][boardX + j] = 1;
        }
    }
    return true;
}

void rotate() {
    vector<vector<int>> rotated(c, vector<int>(r));
    for (int i = 0; i < r; i++) {
        for (int j = 0; j < c; j++) {
            rotated[j][r - 1 - i] = sticker[i][j]; // 90도 회전
        }
    }
    sticker = rotated;
    swap(r, c);
}

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

    cin >> n >> m >> k;
    board.assign(n, vector<int>(m));

    for (int i = 0; i < k; i++) {
        cin >> r >> c;
        sticker.assign(r, vector<int>(c)); // 크기 조정

        for (int j = 0; j < r; j++) {
            for (int l = 0; l < c; l++) {
                cin >> sticker[j][l];
            }
        }

        // 스티커 붙이기
        bool isPasted = false;
        for (int rot = 0; rot < 4; rot++) {
            for (int y = 0; y <= n - r; y++) {
                if (isPasted) break;
                for (int x = 0; x <= m - c; x++) { // x 범위 수정
                    if (IsPossibleFill(x, y)) {
                        isPasted = true;
                        break;
                    }
                }
            }
            if (isPasted) break;
            rotate();
        }
    }

    // 1의 개수 세기
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++) {
            if (board[i][j] == 1) totalCnt++;
        }
    }
    cout << totalCnt;

    return 0;
}

 

... 문제 풀다가 점점 산으로 가는게 느껴져서 부득이하게 동영상 참고해서 풀었다. 처음에는 문제를 잘못 이해했다. 스티커가 주어진 순서대로 붙이라고 문제에서 줬는데 제대로 안 읽어서 백트래킹 이용해야 하는 문제인 줄 알았다;; 

 

그냥 스티커 벡터 하나 만들어놓고 새로운 스티커 입력 받을 때마다 갱신해주면 되는 거였다. 입력 받자마자 해당 스티커를 붙일 수 있는지 확인하고, 붙일 수 있다면 바로 붙이도록 했다. 붙일 수 없는 경우에는 회전을 해줘야 하는데 0, 90, 180, 270 으로 최대 4번까지 확인하게 되는 경우가 있다.

 

시계방향으로 90도 돌리는게 처음에는 되게 어려울 것 같다고 생각했는데 막상 손으로 써보면서 하니까 괜찮았다. 

 

저번에 시뮬레이션 문제 풀었을 때도 느낀거지만 한 문제에 들어가는 시간이 엄청난 것 같다. 시간 엄청 쓰다보면 잘 하고 있는 건지도 잘 모르겠고..;; 아무튼 오늘은 겨우 문제 풀었다.