18808번 스티커 붙이기

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

삼성 sw 역량테스트, 코테, 코딩, 복습, 필수, 추천, BaaaaaaaaaaarkingDog, 코팅테스트, 모의고사, 브루트포스, 시뮬레이션, 구현, boj, 백준

바킹독님의 코딩 테스트 대비 모의고사 1번 문제이다.

바킹독님의 정답 코드 -  https://blog.encrypted.gg/938?category=730176

주석에 설명을 적었다.

0. 제일 첫 스티커는 무조건 원래 모양 그대로 (0, 0)칸이다.

1. 처음에 문제 이해를 못하고, 순서를 고려하지 않은 채 백트래킹 형식으로 구현했었다. 

2. 1번을 고친 후 첫 제출에서 틀렸다. 

알고보니 회전을 한 후 모든 좌표(0,0 ~ R-1,C-1)를 탐색하고 불가능하면 다른 회전을 해야하는데,

(0, 0)에서 출발해서 해당 좌표에 대해서 회전 4번을 모두 탐색하는 형식으로 구현하였고, 붙일 수 있다면 넘어갔었다.

하지만 문제의 의도는 모든 좌표에 대해서 탐색한 후에 적절한 붙일 수 있는 위치가 없다면, 그때, 90도 회전을 해야했다.

3. rt for문을 맨 바깥으로 빼고, 제출하니 정답.

아래는 틀린 코드(여기에서 rt for문을 맨 바깥으로 빼면 정답)

for (int i = 0; i < R && go; i++) {
    for (int j = 0; j < C && go; j++) {
        for (int rt = 0; rt < 4 && go; rt++) {
            if (chk(n, i, j)) {
                draw(n, i, j, n + 1);
                go = false;
 
                backtracking(n + 1);
 
                draw(n, i, j, 0);
            }
 
            rotate(n);
        }
    }
}

#include<bits/stdc++.h>
 
using namespace std;
 
int R, C, K, M[102][12][12], temp[42][42];
pair<int, int> p[102];
int Map[42][42];
/*
R, C, K 입력으로 주어지는 변수들(행, 열, 스티커 개수)
M[a][b][c] = a번 째 스티커에 대한 정보. b = 행, c = 열
temp[a][b] = 스티커를 회전(rotate)할 때 활용하는 임시 행렬
p[a] = a번 째 스티커에 대한 정보(행과 열에 대한 정보 즉, 길이)
Map[a][b] = 노트북(붙여진 스티커들을 알 수 있음)
*/
 
// 스티커를 붙일 수 있는지 검사
bool chk(int n, int a, int b)
{
    // 범위를 벗어나면 당연히 false
    if (a + p[n].first > R || b + p[n].second > C) {
        return false;
    }
 
    // r = i - a, c = j - b 라고 해도 된다.
    for (int i = a, r = 0; i < a + p[n].first; i++, r++) {    
        for (int j = b, c = 0; j < b + p[n].second; j++, c++) {
 
            // Map[i][j]가 1 이상인 것은 이미 스티커가 붙여져 있다는 뜻(스티커는 1 ~ K)
            // 스티커가 붙여져 있거나 붙이려고 하는 스티커의 위치에서 1이라면
            if (Map[i][j] >= 1 && M[n][r][c] == 1) {
                return false;
            }
        }
    }
 
    return true;
}
 
// 스티커 붙이기 or 떼기
void draw(int n, int a, int b, int Put)
{
    // r = i - a, c = j - b 라고 해도 된다.
    // 현재 n번 째 스티커에 대한 정보(p[n])를 활용하여 
    // 노트북에 스티커를 붙이거나(Put = 1 ~ K) 뗀다(Put = 0)
    for (int i = a, r = 0; i < a + p[n].first; i++, r++) {
        for (int j = b, c = 0; j < b + p[n].second; j++, c++) {
 
            // p[n] 활용
            if (M[n][r][c] == 1) {
                Map[i][j] = Put;
            }
        }
    }
}
 
// 스티커가 붙은 칸의 수
int calc()
{
    int ret = 0;
 
    for (int i = 0; i < R; i++) {
        for (int j = 0; j < C; j++) {
 
            // 1 이상일 때
            if (Map[i][j]) {
                ++ret;
            }
        }
    }
    
    return ret;
}
 
// 시계 방향 90도 회전
void rotate(int n)
{
    // 0으로 초기화
    memset(temp, 0, sizeof(temp));
 
    for (int j = 0; j < p[n].second; j++) {
        for (int i = p[n].first - 1; i >= 0; i--) {
            temp[j][p[n].first - i - 1] = M[n][i][j];
        }
    }
 
    for (int i = 0; i < p[n].second; i++) {
        for (int j = 0; j < p[n].first; j++) {
            M[n][i][j] = temp[i][j];
        }
    }
 
    // p[n]에서 first와 second도 바뀐다.
    int tmp = p[n].first;
    p[n].first = p[n].second;
    p[n].second = tmp;
}
 
void backtracking(int n)
{
    // 모든 스티커를 다 사용했다면
    if (n >= K) {
        // 출력하고 끝(유일한 경우)
        printf("%d\n", calc());
        exit(0); // 종료
    }
 
    bool go = true;
 
    for (int rt = 0; rt < 4 && go; rt++) {
        for (int i = 0; i < R && go; i++) {
            for (int j = 0; j < C && go; j++) {
                if (chk(n, i, j)) {
 
                    draw(n, i, j, n + 1); 
                    // n으로 하면 0이 들어가버린다. 테스트하기 쉽게 1로 표현하기 위해 n + 1을 활용,
 
                    go = false; // 안 버려도 되는 스티커. 즉, 붙여지는 스티커
 
                    backtracking(n + 1);
 
                    draw(n, i, j, 0); // 다시 뗀다.
                }
 
            }
        }
 
        // 아직 안 붙여졌다면
        if (go) {
            rotate(n);
        }
    }
 
    // 회전을 다 했지만 붙여지지 않았다면
    if (go) {
        backtracking(n + 1);
    }
}
 
int main()
{
    //freopen("C:\\Users\\park7\\Desktop\\buba.in.6", "r", stdin);
    cin.tie(0);
 
    scanf("%d %d %d", &R, &C, &K);
 
    int r, c, num, idx = 1; // idx는 몇 번째 스티커인지 알 수 있다. idx = 1 ~ K
    for (int d = 0; d < K; d++) {
        scanf("%d %d", &r, &c);
        p[d] = { r, c };
        for (int i = 0; i < r; i++) {
            for (int j = 0; j < c; j++) {
                scanf("%d", &M[d][i][j]);
            }
        }
        ++idx;
    }
 
    backtracking(0);
 
    return 0;
}