[시뮬레이션] C11 백준 18808 스티커 붙이기 풀이

문제

• 18808
• 해당 문제는 시뮬레이션 문제로 상당히 길기 때문에 텍스트로 가져오는건 패스함 링크 참고!

풀이 과정

• 일단 배열이 2개 필요
  • 스티커가 붙을 수 있는지 판별하는 배열(결과값)과 붙이려는 스티커 배열 이렇게 2개
    • 즉, 노트북(nxm), 그리고 스티커(rxc) 배열이 있어야 함
• 문제는 스티커를 4방향으로 회전시켜서 붙여봐야 된다는 건데...
  • 총 4번 시도 필요 (0, 90, 180, 270)
  • 4번 시도 중 1개라도 제대로 붙는다면 결과값 배열에 체크 -> 4번 시도 중 다 안되면 못 붙힘
• 그렇다면 회전을 어떻게 시킬건가?

예를들어 3x3 의 스티커가 들어옴
100
111
100
인 스티커 일 때, 90도로 회전을 시키면
111
010
010
임을 알 수 있음 또 이걸 +90도 회전 시키면
001
111
001
+90도 회전 시키면
010
010
111
이므로

• 잘 보면 규칙이 보이는데, 행, 열을 계속 변경해주면 됨 -> 즉 스티커 자체(3x3)를 회전시키는 구조
• 그렇다면?
  • 스티커 배열을 받는다
  • 스티커 배열을 4번 돌려보면서 노트북에 붙을 수 있는지 없는지 판별한다
    • 붙으면 노트북배열 업데이트
    • 안붙으면 계속, 4번 다 안붙으면 안붙이고 끝냄
  • 끝났으면 노트북배열에 스티커가 있는 부분을 카운팅한다

#include <stdio.h>

#define MAX 41

int n,m,k,r,c;
int laptop[MAX][MAX];
int sticker[11][11];

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

int pastable(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 0;
      }
    }
  }
  
  // 스티커 붙히기
  for (int i=0; i<r; i++) {
    for (int j=0; j<c; j++) {
      if (sticker[i][j] == 1) {
        laptop[x+i][y+j] = 1;
      }
    }
  }
  return 1;
}

int main() {
  scanf("%d %d %d", &n, &m, &k);
  
  while (k--) {
    scanf("%d %d", &r, &c);
    
    for (int i=0; i<r; i++) {
      for (int j=0; j<c; j++) {
        scanf("%d", &sticker[i][j]);
      }
    }
    
    for (int i=0; i<4; i++) {
      int flag = 0;
      for (int x=0; x<=n-r; x++) {
        if (flag == 1) break;
        
        for (int y=0; y<=m-c; y++) {
          if (pastable(x, y)) {
            flag = 1;
            break;
          }
        }
      }
      if (flag == 1) break;
      rotate();
    }
  }
  
  int cnt = 0;
  for (int i=0; i<n; i++) {
    for (int j=0; j<m; j++) {
      if (laptop[i][j] == 1) {
        cnt++;
      }
    }
  }
  printf("%d", cnt);
  
  return 0;
}