[백준] 18808 스티커 붙이기

문제의 출처는 아래와 같다.

 

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

 

출처에 문제를 만든 사람이 유명한 사람이다. 구현과 BFS,DFS 위주의 기업테스트와 유사하게 까다롭게 문제를 만든다.

 

연습용으로 풀어보기 좋으니 풀어보자.

 

이 문제의 설계는 아래와 같다.

1) 격자판을 모두 탐색하면서 조건에 부합하면서 가능한 곳에 색종이를 놓기 (Run()함수)

2) 색종이를 회전시키는 함수 (rotate() 함수)

 

이 두가지를 구현하는 문제이다.

 

이런 구현 문제는 항상 회전이 알맞게 움직이는지, 모든곳을 조건에 맞게 탐색하는지 테스트데이터를 하나 만들어서 확인해야 오류나 에러를 최대한 줄일수 있다. 주석처리로 된곳이 확인한 부분들이다.

 

이외의 부분들은 코드의 주석을 확인하자.

 

 

#include<stdlib.h>
#include<iostream>
#include<string.h>
#include<string>
#include<math.h>
#include<algorithm>
#include<stack>
#include<queue>
#include<map>
#include<set>
#include<iterator>
#include<deque>
#include<sstream>
#pragma warning(disable:4996)
 
using namespace std;
 
int arr[55][55],n,m,k,ans;
int sticker[11][11][101],stick_x[101],stick_y[101];
// 색종이의 값과 각 색종이별 행,열 값을 저장하는 변수
 
void rotate(int a) {
    int tmp[11][11] = { 0 };
    for (int i = 0; i < stick_x[a]; i++) {
        for (int j = 0; j < stick_y[a]; j++) {
            int val = stick_x[a] - (i + 1);
            tmp[j][i] = sticker[val][j][a];
        }
    } // 회전을 했을 때의 결과가 tmp변수에 저장됨
    for (int i = 0; i < stick_x[a]; i++) {
        for (int j = 0; j < stick_y[a]; j++) {
            sticker[i][j][a] = 0;
        }
    }// 원본인 sticker 변수를 0으로 바꿈
    for (int i = 0; i < stick_x[a]; i++) {
        for (int j = 0; j < stick_y[a]; j++) {
            sticker[j][i][a] = tmp[j][i];
        }
    }// 원본인 sticker 변수를 tmp변수로 대입해 회전시킴
    swap(stick_x[a], stick_y[a]);
    // 회전하게되면 행,열의 값들이 바뀜, 그것을 조절
 
    //for (int i = 0; i < stick_x[a]; i++) {
        //for (int j = 0; j < stick_y[a]; j++) {
            //printf("%d ", sticker[i][j][a]);
        //}
        //printf("\n");
    //}
 
}
 
int run(int a,int x,int y) {
    int chk = 0;
    //cout << stick_x[a] << "  " << stick_y[a] << endl;
    for (int i = 0; i < stick_x[a]; i++) {
        for (int j = 0; j < stick_y[a]; j++) { //stick_x, stick_y 는 해당 색종이의 행,열 크기를 가짐
            if (x + i >= n || y + j >= m || (arr[i+x][j+y] == 1 && sticker[i][j][a] == 1)) {
                return 1;
                // 격자판의 (x,y) 에서부터 색종이의 크기만큼 범위 및 겹쳐지는지 확인함
            }
        }
    }// 조건에 안맞는다면 1일 return
    //printf("%d\n", chk);
    //cout << stick_x[a] << "  " << stick_y[a] << endl;
    for (int i = 0; i < stick_x[a]; i++) {
        for (int j = 0; j < stick_y[a]; j++) {
            if (sticker[i][j][a] == 1) arr[i+x][j+y] = 1;
        }
    }// 조건에 일치한다면 격자판에 해당 색종이를 삽입
    return 0;
}
 
int main()
{
    cin >> n >> m >> k;
    for (int i = 0; i < k; i++) {
        scanf("%d %d", &stick_x[i], &stick_y[i]);
        for (int j = 0; j < stick_x[i]; j++) {
            for (int z = 0; z < stick_y[i]; z++) {
                scanf("%d", &sticker[j][z][i]);
            }
        }
    }
    //rotate(3);
    //rotate(3);
    //rotate(3);
    
    
    for (int z = 0; z < k; z++) {// z번쨰 색종이별로 순서대로 순회
        int skip = 0;
        //printf("%d : ", z);
        for (int g = 0; g < 4; g++) { // 처음 상태의 색종이와 90,180,270 도 회전을 위한 반복문
            //cout << g << endl;
            //if (g == 3) {
                //for (int s = 0; s < stick_x[z]; s++) {
                    //for (int ss = 0; ss < stick_y[z]; ss++) {
                        //printf("%d ", sticker[s][ss][z]);
                    //}
                    //printf("\n");
                //}
            //}
            if (skip == 1) break; // 이미 색종이를 붙힌상태라면 빠져나감
            for (int i = 0; i < n; i++) {
                for (int j = 0; j < m; j++) { // 각 격자판 시작 지점들, 왼쪽 위부터니 2중 for문을 그대로 사용하면 됨
                    if (skip == 1) break;
                    if (run(z, i, j) == 0) {// z번째 색종이를 격자판의 (i,j) 부터 시작
                        skip = 1;
                        break;
                    }
                }
            }
            rotate(z); // 회전
        }
    }
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++) {
            if (arr[i][j] == 1) ans++;
            //printf("%d ", arr[i][j]);
        }
        //printf("\n");
    }
    cout << ans;
    return 0;
}