[BOJ / C++] 스티커 붙이기 (시뮬레이션)

문제링크: https://www.acmicpc.net/problem/18808

 

1. 코드

#include <bits/stdc++.h>
using namespace std;

bool possible(vector<vector<int>>& board, vector<vector<int>>& sticker, int stR, int stC, int r, int c) {
    for (int i = 0; i < r; i++) {
        for (int j = 0; j < c; j++) {
            if (board[stR+i][stC+j] == 1 && sticker[i][j] == 1) return false;
        }
    }
    return true;
}

void rotate(vector<vector<int>>& sticker, int& r, int& c) {
    vector<vector<int>> tmp(40, vector<int>(40, 0));
    for (int i = 0; i < r; i++) {
        for (int j = 0; j < c; j++) {
            tmp[i][j] = sticker[i][j];
        }
    }

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

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

    int n, m, k;
    cin >> n >> m >> k;

    vector<vector<int>> board(40, vector<int>(40, 0));

    while (k--) {
        int r, c;
        cin >> r >> c;
        vector<vector<int>> sticker(10, vector<int>(10, 0));
        
        for (int i = 0; i < r; i++) {
            for (int j = 0; j < c; j++) {
                cin >> sticker[i][j];
            }
        }

        bool paste = false;
        for (int dir = 0; dir < 4; dir++) {
            // 붙일 수 있는지 검사
            for (int i = 0; i < n-r+1; i++) {
                for (int j = 0; j < m-c+1; j++) {
                    if (possible(board, sticker, i, j, r, c)) {
                        
                        // 스티커 붙이기
                        for (int x = 0; x < r; x++) {
                            for (int y = 0; y < c; y++) {
                                if (sticker[x][y] == 1) board[i+x][j+y] = sticker[x][y];
                            }
                        }

                        paste = true;
                        break;
                    }
                }
                if (paste) break; 
            }

            if (paste) break; 
            rotate(sticker, r, c); // 회전
        }
    }


    int cnt = 0;
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++) {
            if (board[i][j] == 1) cnt++;
        }
    }
    cout << cnt;
}

 

 

2. 분석

1. 스티커를 회전시키지 않고 모눈종이에서 떼어낸다.
2. 다른 스티커와 겹치거나 노트북을 벗어나지 않으면서 스티커를 붙일 수 있는 위치를 찾는다. 혜윤이는 노트북의 위쪽부터 스티커를 채워 나가려고 해서, 스티커를 붙일 수 있는 위치가 여러 곳 있다면 가장 위쪽의 위치를 선택한다. 가장 위쪽에 해당하는 위치도 여러 곳이 있다면 그중에서 가장 왼쪽의 위치를 선택한다.
3. 선택한 위치에 스티커를 붙인다. 만약 스티커를 붙일 수 있는 위치가 전혀 없어서 스티커를 붙이지 못했다면, 스티커를 시계 방향으로 90도 회전한 뒤 2번 과정을 반복한다.
4. 위의 과정을 네 번 반복해서 스티커를 0도, 90도, 180도, 270도 회전시켜 봤음에도 스티커를 붙이지 못했다면 해당 스티커를 붙이지 않고 버린다.

문제에 나와있는 위 4가지를 순서대로 구현해주면 된다. sticker를 입력받아서 board에서 붙일 수 있는지 없는 지를 검사한다. 이때 index 범위에 주의한다.(i < n+1-r, j < m+1-c) 이후 붙일 수 있으면 board에 sticker 패턴을 업데이트 해준다. 스티커를 붙였으면 break를 통해 탈출하고, 아니면 rotate 함수를 통해 스티커를 회전시켜서 다시 검사한다.

 

※ rotate 함수 구현할 때는 직접 예시 상황에 대해 index를 써보고 어떻게 변화하는지를 패턴을 파악해 구현해야한다.

 

3. 시간복잡도

최대 연산 수는 (스티커갯수) * (방향검사: 4) * (스티커를 board에 붙일 수 있는지 검사: n*m) * (스티커 붙이기: r*c)이고, 계산해보면 100 * 4 * 40 * 40 * 10 * 10 * 100 = 64,000,000 < 10^8 이므로 시간제한 2초 안에 통과가 가능하다.