[BOJ] 18808 : 스티커 붙이기

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

---

시뮬레이션

[ 문제해석 ]

 map에 입력된 스티커를 붙이는데 이미 스티커가 없는 부분에만 스티커를 붙일 수 있고, 스티커가 범위 밖으로 나가도 안된다. 스티커를 붙일 수 있는 지점이 여러 곳이 있다면 위쪽, 왼쪽에 우선순위를 주어 스티커를 붙이고, 현재 스티커를 붙일 지점이 없다면 스티커를 90도 씩 회전시켜서 확인해본다. 90도 씩 4번 회전해서 원래 모양으로 돌아왔는데도 붙일 지점이 없었다면 스티커를 버린다.

 

[ 알고리즘풀이 ]

 일단 Input 크기가 굉장히 작다 --> 단순 시뮬레이션으로 모든 경우를 커버해도 된다.

 

 1) 위쪽 / 왼쪽에 우선순위를 주어 스티커를 붙여야 하므로, 스티커를 map의 좌측 상단부터 시작해서 차례대로 모든 지점에서 스티커를 붙여본다.

 2) 스티커를 붙일 수 있다면, 붙이고 map에 체크해주고 넘어간다.

 3) 스티커를 붙일 수 없다면, rotate를 시켜서 다시 1) 과정을 거친다. 이때, 주의할 부분은 rotate를 시키면 기존의 스티커 행과 열이 바뀌게 된다! 예를 들어, 5x2 크기의 스티커는 2x5 크기로 바뀐다. 

 4) rotate를 4번 진행했는데도 붙일 수 없다면 다음 스티커로 넘어간다.

 

[ 코드 C++ ]

#include<iostream>
 
using namespace std;
 
int main(void) {
    ios::sync_with_stdio(false);
    cin.tie(0); cout.tie(0);
 
    int mapRows, mapCols, stickers;
    bool map[40][40] = {};
    cin >> mapRows >> mapCols >> stickers;
    for (int sticker = 0; sticker < stickers; sticker++) {
        // 스티커 입력
        int stickerRows, stickerCols;
        bool stickerMap[10][10] = {};
        cin >> stickerRows >> stickerCols;
        for (int stickerR = 0; stickerR < stickerRows; stickerR++)
            for (int stickerC = 0; stickerC < stickerCols; stickerC++)
                cin >> stickerMap[stickerR][stickerC];
 
        // 4방향에 대해서 스티커를 위, 왼쪽부터 붙여보자.
        for (int rotate = 0; rotate < 4; rotate++) {
            bool success = false;
            for (int j = 0; j <= mapRows - stickerRows; j++) {
                for (int k = 0; k <= mapCols - stickerCols; k++) {
                    // map의 (j,k) 에서 시작해서 스티커를 붙여보자.
                    bool fail = false;
                    for (int stickerR = 0; stickerR < stickerRows; stickerR++) {
                        for (int stickerC = 0; stickerC < stickerCols; stickerC++) {
                            // 이미 스티커가 붙은 곳에 붙여야하는 경우
                            if (map[j + stickerR][k + stickerC] && stickerMap[stickerR][stickerC]) { 
                                fail = true;
                                stickerR = stickerRows, stickerC = stickerCols;
                            }
                        }
                    }
                    if (!fail) {
                        for (int stickerR = 0; stickerR < stickerRows; stickerR++)
                            for (int stickerC = 0; stickerC < stickerCols; stickerC++)
                                if (stickerMap[stickerR][stickerC]) map[j + stickerR][k + stickerC] = 1;
                        j = mapRows - stickerRows + 1, k = mapCols - stickerCols + 1; //break;
                        success = true;
                    }
                }
            }
            if (success) break;
 
            // 90도 회전시키자
            bool copyStickerMap[10][10] = {};
            for(int stickerR = 0; stickerR < stickerCols; stickerR++)
                for(int stickerC = 0; stickerC < stickerRows; stickerC++)
                    copyStickerMap[stickerR][stickerC] = stickerMap[stickerRows- 1 - stickerC][stickerR];
            int temp = stickerRows; // 회전하니까 row, col SWAP
            stickerRows = stickerCols;
            stickerCols = temp;
            for (int stickerR = 0; stickerR < 10; stickerR++) // 회전시킨 copyMap 복사해주기
                for (int stickerC = 0; stickerC < 10; stickerC++)
                    stickerMap[stickerR][stickerC] = copyStickerMap[stickerR][stickerC];
 
        }
    }
    int ans = 0;
    for (int mapR = 0; mapR < mapRows; mapR++)
        for (int mapC = 0; mapC < mapCols; mapC++)
            if (map[mapR][mapC]) ans++;
 
    cout << ans << '\n';
}

[ github ]

https://github.com/travelbeeee/BOJ/blob/master/BOJ18808.cpp

travelbeeee/BOJ

---