BOJ-18808 스티커 붙이기

접근

• 도형을 회전하는 규칙과 스티커 저장방법만 잘 설계하고 구현해내면 해결가능한 문제였다.
• 두개의 구조체를 사용했는데 하나는 좌표를 저장하기위한 구조체 하나는 스티커 정보를 담을 구조체 이다.

struct pos{
    int y,x; //점의 좌표
};
struct sticker{
    int y,x; //스티커의 세로,가로 길이
    vector<pos>v; //y by x 형태의 행렬에서 스티커가 내용이 있는 부분의 좌표
};

• sticker구조체에서 스티커가 색이 있는 부분을 좌표로 저장하게하고, 이로 인해 90도씩 회전하는 부분의 구현이 쉬워졌던것 같다.

• 90도 회전규칙은 아래와 같다. 여러 문제를 풀면서 구현을 해본적있지만 머리에 잘 안 외워지는 것 같다.

  y 좌표 : 현재 x좌표값
  x 좌표 : 회전했을때 스티커의 가로길이 - 현재 y좌표값

• 코드로 나타내면 아래와 같다.

swap(cur.v[i].y,cur.v[i].x);
cur.v[i].x = cur.x-cur.v[i].x-1;

코드(C++)

#include <iostream>
#include <vector>
#define FIO  ios_base::sync_with_stdio(false), cin.tie(NULL), cout.tie(NULL)
using namespace std;
int n,m,k,p,arr[41][41],ans;
struct pos{
    int y,x;
};
struct sticker{
    int y,x;
    vector<pos>v;
};
vector<sticker>stickers;
int main(){
    FIO;
    cin>>n>>m>>k;
    for(int i=0;i<k;i++){
        sticker tmp;
        cin>>tmp.y>>tmp.x;
        for(int i=0;i<tmp.y;i++){
            for(int j=0;j<tmp.x;j++){
                cin>>p;
                if(p) tmp.v.push_back({i,j});
            }
        }
        tmp.cnt=0;
        stickers.push_back(tmp);
    }
    
    for(auto cur: stickers){
        bool flag = false;
        //위치 탐색
        for(int d=0;d<4;d++){
            //회전
            if(d){
                swap(cur.y,cur.x);
                for(int i=0;i<cur.v.size();i++){
                    swap(cur.v[i].y,cur.v[i].x);
                    cur.v[i].x = cur.x-cur.v[i].x-1;
                }
            }

            for(int i=0;i<n-(cur.y-1);i++){
                for(int j=0;j<m-(cur.x-1);j++){
                    //스티커 붙일 수 있는지 확인
                    flag = true;
                    for(auto it:cur.v){
                        if(arr[i+it.y][j+it.x]){
                            flag = false;
                            break;
                        }
                    }
                    //붙일수있다면 붙이고 넘어감
                    if(flag){
                        for(auto it:cur.v) arr[i+it.y][j+it.x]=1;
                        break;
                    }
                }
                if(flag) break;
            }
            //붙였다면 건너뛰기
            if(flag) break;
        }
    }
    
    //남은공간 카운트
    for(int i=0;i<n;i++) for(int j=0;j<m;j++) if(arr[i][j]) ans+=1;
    cout<<ans<<"\n";
    return 0;
}

결과