[ BOJ18808 스티커 붙이기 ]

문제 분석

특별한 아이디어가 필요하지는 않았다.
2차원 배열을 회전 시키는 방법을 알고 있고!
문제를 꼼꼼히 읽어가면서 풀었다면 정확하게 풀 수 있다.

시간 복잡도

각각의 칸에 대하여 : 40 x 40
각 스티커가 붙을 수 있는지 확인 : 10 x 10
4가지 방향으로 돌려서 확인 : 4 x 10 x 10
스티커의 갯수 : 100

구현

2차원 배열의 회전

헤맸던 부분

일단 2차원 배열을 어떻게 회전 시켜야 되는지 방법을 찾지 못했다.
문제를 꼼꼼히 읽지 않았다.
반복문을 돌릴때 모든 칸에 대해서 스티커를 붙일 수 있는지 확인을 하고 회전을 돌렸어야 했는데 그러지 않고 한칸에 대해서 스티커를 모두 돌려본 후 다음 칸으로 이동했다.

얻은 것

2차원 배열의 회전

전체 코드

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

int Row;
int Col;
int S_cnt;

int Board[42][42];
int S_info[102][12][12];
int S_info_origin[102][12][12];

vector<pair<int,int> > S_size_info;
vector<pair<int,int> > S_size_info_origin;

void init(){
    ios::sync_with_stdio(0);
    cin.tie(0);
}

void get_s_info(int s){
    int row, col;
    cin >> row >> col;
    S_size_info.push_back(make_pair(row,col));
    S_size_info_origin.push_back(make_pair(row,col));

    for(int i = 0 ; i < row; i++){
        for(int j = 0 ; j < col; j++){
            cin >> S_info[s][i][j];
            S_info_origin[s][i][j] = S_info[s][i][j];
        }
    }
}

void return_to_origin(int s){
    int row = S_size_info_origin[s].first;
    int col = S_size_info_origin[s].second;

    for(int i = 0 ; i < row; i++){
        for(int j = 0 ; j < col; j++){
            S_info[s][i][j] = S_info_origin[s][i][j];
        }
    }

    S_size_info[s].first = row;
    S_size_info[s].second = col;
}

void get_input(){
    cin >> Row >> Col >> S_cnt;
    for(int i = 0; i < S_cnt; i++){
        get_s_info(i);
    }
}

int check(int s_num, int r_cor, int c_cor){

    int row = S_size_info[s_num].first;
    int col = S_size_info[s_num].second;

    for(int i = 0 ; i < row; i++){
        for(int j = 0 ; j < col; j++){

            int cur_row = r_cor + i;
            int cur_col = c_cor + j;

            if(cur_row >= Row || cur_col >= Col) return 0;

            if(S_info[s_num][i][j] == 0) continue;

            if(Board[cur_row][cur_col] >= 1) return 0;

        }
    }

    return 1;
}

void mark(int s_num, int r_cor, int c_cor, int marker){

    int row = S_size_info[s_num].first;
    int col = S_size_info[s_num].second;

    for(int i = 0 ; i < row; i++){
        for(int j = 0 ; j < col; j++){
            if(S_info[s_num][i][j] == 0) continue;
            Board[r_cor + i][c_cor + j] = marker;
        }
    }
}

void rotate_90(int s_num){
    int tmp[12][12];

    int row_size = S_size_info[s_num].first;
    int col_size = S_size_info[s_num].second;

    for(int i = 0 ; i < row_size ; i++){
        for(int j = 0 ; j < col_size; j++){
            tmp[j][row_size-1-i] = S_info[s_num][i][j];
        }
    }

    for(int i = 0 ; i < col_size ; i++){
        for(int j = 0 ; j < row_size; j++){
            S_info[s_num][i][j] = tmp[i][j];
        }
    }

    int temp = S_size_info[s_num].first;
    S_size_info[s_num].first = S_size_info[s_num].second;
    S_size_info[s_num].second = temp;
}

int main(void){
    init();
    get_input();
    
    for(int s = 0 ; s < S_cnt; s++){
        int fit = 0;
        for(int rot = 0 ; rot < 4; rot++){
            if(fit) break;
            for(int r = 0 ; r < Row; r++){
                if(fit) break;
                for(int c = 0 ; c < Col; c++){
                    if(fit) break;
                    if(check(s,r,c)){
                        fit = 1;
                        mark(s,r,c,s+1);
                    }
                }
            }
            rotate_90(s);
        }
    }

    int ans = 0;
    for(int i = 0 ; i < Row; i++){
        for(int j = 0; j < Col; j++){
            if(Board[i][j] != 0) ans++;
        }
    }

    cout << ans << "\n";

}