BOJ 18808) 스티커 붙이기 (C++)

18808번: 스티커 붙이기

 구현 문제이다. 처음엔 돌리는걸 직접 구현하지 않고 노트북에 스티커를 붙여보는 단계에서 i, j를 조절해서 해결하려 하였으나 생각보다 신경쓸 부분이 많아서 스티커를 돌리는걸로 변경했다. 스티커를 돌리는 부분에서 i, j가 헷갈려서 또 한참 헤맸다. 

 각 스티커에 대해 붙일 수 있는지 검토한다(stick). 붙일 수 있는 공간이 있으면 붙이고 다음 스티커의 검토로 넘어가고 그렇지 않으면 스티커를 회전시켜 다시 시도한다. 스티커를 회전시킬 때 i, j가 어떤식으로 바뀌어야 하는지 주의한다. 스티커를 회전시키고 나면 가로 세로 길이도 바꿔준다. 90 180, 270도 회전을 한 뒤에도 붙이지 못하면 다음 스티커로 넘어간다. 

 스티커를 붙일 수 있는 공간을 찾으면 빈칸에 스티커를 붙이고 붙은 영역의 갯수(ans)를 1 증가시킨다.

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

int N, M, K, r, c, ans, cnt;
bool laptop[41][41];
bool sticker[11][11];
bool temp[11][11];

void rotate(){
  memset(temp, 0, sizeof(temp));
  for(int i=0;i<c; i++){
    for(int j=0;j<r;j++){
      temp[i][j]=sticker[r-1-j][i];
    }
  }
  memset(sticker, 0, sizeof(sticker));
   for(int i=0;i<c; i++){
    for(int j=0;j<r;j++){
      sticker[i][j]=temp[i][j];
    }
  }
  int temp =r;
  r=c;
  c=temp;
}

bool stick(int x, int y){
  for(int i=0;i<r;i++){
    for(int j=0;j<c;j++){
      if(laptop[x+i][y+j]==1&&sticker[i][j]==1) return false;
    }
  }
  for(int i=0;i<r;i++){
    for(int j=0;j<c;j++){
      if(!laptop[x+i][y+j]&&sticker[i][j]) {
        laptop[x+i][y+j]=1;
        ans++;
      }
    }
  }
  return true;
}

void start(){
  int i=0,j=0,k=0;
  bool chk = false;
  while(!chk&&k<4){
    i=0;j=0;
    while(!chk&&(i<=N-r&&j<=M-c)){
      chk = stick(i,j);
      if(j==M-c){
        i+=1; j=0;
      } else {
        j++;
      }
    }
    if(!chk) rotate();
    k++;
  }
}

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

  cin>>N>>M>>K;
  for(int i=0;i<K;i++){
    cin>>r>>c;
    cnt=0;
    memset(sticker, 0, sizeof(sticker));
    for(int j=0;j<r;j++){
      for(int k=0;k<c;k++){
        cin>>sticker[j][k];
        if(sticker[j][k]) cnt++;
      }
    }
    start();
  }
 

  cout<<ans;
  return 0;
}