[BOJ] 18808. 스티커 붙이기

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

18808번: 스티커 붙이기

백준에서 BaaaaaaaaaaarkingDog님이 코딩 테스트 대비 모의고사로 출제하신 시뮬레이션 문제이다. 대회가 열렸을 때 들어가서 풀어봤는데 재밌었다. 총 두 문제였는데 나머지 한 문제는 18809번 Gaaaaaaaaaarden (문제 링크)이다. (풀이 링크)

스티커 붙이기 문제가 좀 더 쉽다. 

 

 

 

먼저 매번

 sticker를 저장할 int배열 / 모니터에 스티커가 붙여졌는지 확인할 bool 배열 / 스티커를 90도 회전시킬 때 임시로 사용할 int 배열

이렇게 세 가지 배열을 사용하였다.

 

 

문제에서 나와있는 스티커를 붙이는 조건은 다음과 같다.

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

 

 

위의 조건에 따라 먼저 입력받은 스티커를 노트북의 위쪽부터 붙일 수 있는지 확인한다. 

(0, 0)부터 (N-R, M-C) 칸까지 각 칸을 스티커의 시작점으로 했을 때의 스티커를 붙이는 경우를 순차적으로 해보고

붙일 수 있다면 바로 그 자리에 붙인다. 문제 조건에서 스티커를 붙일 우선순위는 가장 먼저 가장 위쪽, 그다음에 가장 왼쪽이므로 일반적인 for문으로 돌리고 찾는 순간 바로 탐색을 종료하면 자연스럽게 구현할 수 있다.

 

 

 

스티커를 붙일 수 있는지는 단순히 스티커를 저장해놓은 배열과 모니터에 스티커가 붙어있는지 확인할 배열을 비교해주면 된다.

비교할 때나 모니터에 스티커를 붙여줄 때, 확인할 모니터의 시작점을 주의해야 한다.

스티커는 매번 (0, 0)부터 검사해주면 되지만 모니터는 스티커를 붙이기 시작하는 칸부터 검사해야 하므로

스티커를 모니터의 (x, y) 칸부터 붙여본다고 한다면 스티커의 (i, j)를 확인할 때는 모니터의(i+x, j+y) 칸을 비교해주어야 한다.

 

 

 

모니터에 이미 스티커가 있는데 모눈종이 위에도 스티커가 있다면 붙일 수 없으므로 바로 false를 리턴해서 다음 경우로 넘어간다.

붙일 수 있다면 모니터에 스티커를 붙여주고 다음 스티커로 넘어간다.

 

 

 

모든 칸에서 시작해도 스티커를 붙일 수 없다면 90도 회전해서 똑같은 과정을 반복한다.

90도씩 회전시켜서 모든 경우(0도, 90도, 180도, 270도)를 해봤는데도 붙일 수 없다면 문제 조건에 따라 해당 스티커는 버린다.

 

 

90도 회전을 시킬 때는 위의 그림과 같이 tmp배열의 index를 기준으로 복사해줬다.

90도 회전하게 되면 행의 수(R)와 열의 수(C)가 되므로 for문에서 i는 C 전까지, j는 R 전까지 해주면 된다.

for문을 이용해서 tmp배열은 순차적으로 채워주면 되고, 스티커 배열은 i와 추가적인 변수 l 을 사용해서 위의 그림에 나와있는 순서대로 값이 들어가도록 구현했다. 코드로 보면 다음과 같다.

 

for (int i = 0; i < c; i++) {

        for (int j = 0, l = r-1; j < r; j++, l--) {

            tmparr[i][j] = sticker[l][i];

        }

    }

 

tmp배열에 모두 복사했다면 R과 C의 값을 아예 바꿔주고 tmp배열의 값을 원래 스티커 배열로 다시 옮겨준다.

 

 

 

k번의 스티커를 모두 붙여 본 후에 모니터에 스티커가 붙여져 있는지 확인하는 배열을 검사해서 최종 답을 구한다.

#include <iostream>
#include <cstring>
using namespace std;
 
int n, m, k;
int r, c;
 
bool map[40][40];
int sticker[10][10];
int tmparr[10][10];
 
 
void rotate() {
    memset(tmparr, 0, sizeof(tmparr));
 
    //회전시킨 모양을 tmparr에 임시 저장
    for (int i = 0; i < c; i++) {
        for (int j = 0, l = r-1; j < r; j++, l--) {
            tmparr[i][j] = sticker[l][i];
        }
    }
 
    //90도 회전하므로 행과 열을 바꿔준다
    int tmp = r;
    r = c;
    c = tmp;
 
    //다시 스티커 배열에 tmparr배열을 복사
    memset(sticker, 0, sizeof(sticker));
    for (int i = 0; i < r; i++) {
        for (int j = 0; j < c; j++) {
            sticker[i][j] = tmparr[i][j];
        }
    }
}
 
 
void putSticker(int x, int y) {
    for (int i = 0; i < r; i++) {
        for (int j = 0; j < c; j++) {
            //모눈 종이에서 스티커인 부분(1)을 노트북에 붙인다
            if (sticker[i][j] == 1) map[i + x][j + y] = true;
        }
    }
}
 
 
bool check(int x, int y) {
    for (int i = 0; i < r; i++) {
        for (int j = 0; j < c; j++) {
            //스티커를 붙일 곳에 이미 스티커가 붙어있다면 바로 false를 리턴
            if (map[i + x][j + y] && sticker[i][j] == 1) return false;
        }
    }
    return true;
}
 
 
bool solve() {
    for (int i = 0; i <= n - r; i++) {
        for (int j = 0; j <= m - c; j++) {
            //i,j를 시작점으로 스티커를 붙여본다.
            if (check(i, j)) {
                //스티커를 붙일 수 있다면 붙이고 바로 true를 리턴
                putSticker(i, j);
                return true;
            }
        }
    }
    return false;
}
 
 
int main() {
    ios_base::sync_with_stdio(false);
    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];
            }
        }
 
 
        bool flag = false;
        for (int i = 0; i < 4; i++) {
            flag = solve();
 
            //붙일 수 있는 곳이 있다면 break
            if (flag) break;
            else rotate(); //붙일 수 있는 곳이 없다면 90도 회전
        }
 
 
    }
 
 
    int ans = 0;
    //스티커가 붙어 있는 칸을 센다.
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++) {
            if (map[i][j]) ans++;
        }
    }
 
 
    cout << ans << '\n';
    
 
    return 0;
}