[백준 18808번] 스티커 붙이기 (C/C++)

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

18808번: 스티커 붙이기

---

전체 알고리즘의 기본 틀은 아래와 같습니다.

1. 스티커의 각 좌표를 구한다. 
2. 노트북에 붙여본다.
3. 실패한다면 각 좌표를 90° 시킨다. 2번 부터 다시 진행한다. (단, 360° 회전시킨 경우, 더이상 노트북에 붙여보지 않는다.)

아래는 각 좌표를 90° 회전시키는 함수입니다. 

⚠️ 주의할 점은 이후에 또 다시 각 좌표를 90° 회전시킬 수 있기 때문에 n과 m을 교환해주어야 한다는 것입니다.  

void rotate(vector<pair<int, int>>& pos, int* n, int* m){ 
    for(int i = 0; i < pos.size(); i++){
        int nx = pos[i].y; int ny = (*n - 1) - pos[i].x;
        pos[i].x = nx; pos[i].y = ny;
    }

    int temp = *n; *n = *m; *m = temp;
}

 

다음으로 노트북에 스티커를 붙이는 함수입니다. 

스티커를 붙이는 기준 좌표를 하나씩 이동시켜가면서, 스티커를 붙일 수 있는지 확인하고, 붙일 수 있다면 해당 좌표들을 1로 표시하고 True를 반환합니다. 모든 기준 좌표를 확인해도 스티커를 붙일 수 없다면, False를 반환합니다.

bool attach(vector<pair<int, int>> pos){
    bool flag = false;
    for(int i = 0; i < n; i++){ // 기준 좌표는 {i, j}, 기준 좌표를 이동시키면서 스티커를 붙여봄
        for(int j = 0; j < m; j++){
            flag = true;    // 스티커를 붙일 수 있는지를 나타내는 flag
            for(auto c : pos){
                // 기준 좌표를 (0, 0)으로 잡았을 때 각 좌표의 새로운 좌표
                int nx = i + c.x; int ny = j + c.y;   

                // 이미 스티커가 붙어있거나, 노트북의 범위를 벗어나는 경우 flag를 false로 설정
                if(notebook[nx][ny] == 1 || nx < 0 || ny < 0 || nx >= n || ny >= m) 
                    flag = false;   
            }

            if(flag){   // 노트북에 스티커를 붙일 수 있다면
                for(auto c : pos){  
                    int nx = i + c.x; int ny = j + c.y;
                    notebook[nx][ny] = 1;   // 스티커를 붙임
                }
                return true;
            }
        }
    }
    return false;
}

 

 

아래는 전체 코드입니다.

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

#define x first
#define y second

int notebook[40][40];   // 스티커를 붙일 노트북
int n, m, k;

void rotate(vector<pair<int, int>>& pos, int* n, int* m){ 
    for(int i = 0; i < pos.size(); i++){
        int nx = pos[i].y; int ny = (*n - 1) - pos[i].x;
        pos[i].x = nx; pos[i].y = ny;
    }

    int temp = *n; *n = *m; *m = temp;
}

bool attach(vector<pair<int, int>> pos){
    bool flag = false;
    for(int i = 0; i < n; i++){ // 기준 좌표는 {i, j}, 기준 좌표를 이동시키면서 스티커를 붙여봄
        for(int j = 0; j < m; j++){
            flag = true;    // 스티커를 붙일 수 있는지를 나타내는 flag
            for(auto c : pos){
                // 기준 좌표를 (0, 0)으로 잡았을 때 각 좌표의 새로운 좌표
                int nx = i + c.x; int ny = j + c.y;   

                // 이미 스티커가 붙어있거나, 노트북의 범위를 벗어나는 경우 flag를 false로 설정
                if(notebook[nx][ny] == 1 || nx < 0 || ny < 0 || nx >= n || ny >= m) 
                    flag = false;   
            }

            if(flag){   // 노트북에 스티커를 붙일 수 있다면
                for(auto c : pos){  
                    int nx = i + c.x; int ny = j + c.y;
                    notebook[nx][ny] = 1;   // 스티커를 붙임
                }
                return true;
            }
        }
    }
    return false;
}

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

    cin >> n >> m >> k;

    while(k--){ // 스티커 개수만큼 반복
        int tn, tm; cin >> tn >> tm;    // 스티커의 크기 입력 받음
        int board[10][10];  

        for(int i = 0; i < tn; i++)
            for(int j = 0; j < tm; j++)
                cin >> board[i][j]; // 스티커 입력 받음

        vector<pair<int, int>> pos;
        for(int i = 0; i < tn; i++)
            for(int j = 0; j < tm; j++)
                if(board[i][j] == 1) pos.push_back({i, j}); // 스티커의 각 좌표 push

        for(int i = 0; i < 4; i++){
            bool success = attach(pos); // 노트북에 스티커를 붙임
            if(success) break;  // 붙이기에 성공한 경우, 각 좌표를 회전시키지 않고 break
            else rotate(pos, &tn, &tm); // 붙이기에 실패한 경우, 각 좌표를 회전시킴
        }
    }

    int ans = 0;
    for(int i = 0; i < n; i++)
        for(int j = 0; j < m; j++)
            if(notebook[i][j] == 1) ans++; // 스티커가 붙은 칸 수 count

    cout << ans << "\n";
}