[BOJ] 15898 : 피아의 아틀리에 ~신비한 대회의 연금술사~

문제 : https://www.acmicpc.net/problem/15898

---

#구현 #시뮬레이션

[ 문제해석 ]

5 x 5 가마에 4 x 4 크기의 재료들을 넣어서 폭탄을 제조한다. 이때, 4 x 4 크기의 재료는 가마의 격자를 벗어날 수 없고, 회전해서 넣을 수 있고 서로 다른 재료를 3가지 가마에 넣는다.

 

[ 알고리즘핵심 ]

4 x 4 크기의 재료는 최대 10개이고 회전해서 넣을 수 있으므로 최대 40개(회전시킨재료포함)의 재료에서 3가지 재료를 뽑는다고 생각해도 된다. 그 후, 이 재료들을 5 x 5 가마에 넣어야되는데 이때도 가마의 (0, 0) / (0, 1) / (1, 0) / (1, 1) 에 재료를 넣는 경우를 제외하고는 가마를 다 벗어난다.

 따라서, 백트레킹을 이용해 40개에서 3개를 뽑고, 4가지 위치 중에 하나를 고르는 모든 경우의 수를 구해도 복잡도가 40C3 * 4^3 밖에 나오지 않는다. 즉, 1초 안에 가능한 연산이다.

 

[ 알고리즘풀이 ]

1. 입력을 받으면 시계방향으로 90도, 180도, 270도 회전한 상태도 같이 effect, color 배열에 저장해준다.

2. 백트레킹1 - 백트레킹을 이용해 재료 3개를 뽑는다. 

3. 백트레킹2 - 재료 3개를 다 뽑은 상태에서, 재료 3개의 넣는 위치를 구한다.

4. 플레이게임 - 'W'로 초기화된 가마를 만든 후, 3가지 재료를 정해진 위치에 넣고 red, blue, green, yellow 효능 값을 구해주면 된다.

#include<iostream>
#include<algorithm>
#include<vector>
 
using namespace std;
 
int n, ans;
int dx[4] = { 0, 0, 1, 1 }, dy[4] = { 0, 1, 0, 1 };
int effect[40][4][4];
char color[40][4][4];
bool choosenMaterial[10];
vector<int> v, v2;
 
void turnClockwise(int index, int turn) {
    if (turn == 3) return;
    for (int i = 0; i < 4; i++)
        for (int j = 0; j < 4; j++) {
            effect[index + 1][i][j] = effect[index][3 - j][i];
            color[index + 1][i][j] = color[index][3 - j][i];
        }
    turnClockwise(index + 1, turn + 1);
}
 
void playGame(void) {
    int effectMap[5][5] = {};
    char colorMap[5][5] = {};
    for (int i = 0; i < 5; i++)
        for (int j = 0; j < 5; j++) colorMap[i][j] = 'W';
 
    for (int i = 0; i < 3; i++) {
        // Map에 재료를 넣자.
        int sX = dx[v2[i]], sY = dy[v2[i]];
 
 
        for(int j = 0; j < 4;j++)
            for (int k = 0; k < 4; k++) {
                if (color[v[i]][j][k] != 'W') colorMap[sX + j][sY + k] = color[v[i]][j][k];
                effectMap[sX + j][sY + k] += effect[v[i]][j][k];
                if (effectMap[sX + j][sY + k] < 0) effectMap[sX + j][sY + k] = 0;
                if (effectMap[sX + j][sY + k] > 9) effectMap[sX + j][sY + k] = 9;
            }
    }
    int red = 0, blue = 0, green = 0, yellow = 0;
    for (int i = 0; i < 5; i++) {
        for (int j = 0; j < 5; j++)
            if (colorMap[i][j] == 'R') red += effectMap[i][j];
            else if (colorMap[i][j] == 'B') blue += effectMap[i][j];
            else if (colorMap[i][j] == 'G') green += effectMap[i][j];
            else if (colorMap[i][j] == 'Y') yellow += effectMap[i][j];
    }
 
    ans = max(ans, 7 * red + 5 * blue + 3 * green + 2 * yellow);
    return;
}
// 뽑은 3개의 재료를 (0, 0), (0, 1), (1, 0), (1, 1) 중 어디에 놓을지 정한다.
void backtracking2(void) {
    if (v2.size() == 3) {
        playGame();
        return;
    }
    for (int i = 0; i < 4; i++) {
        v2.push_back(i);
        backtracking2();
        v2.pop_back();
    }
}
// n개의 재료를 회전시킨 4 * n 경우의 수 중 3개를 뽑는다.
void backtracking1(void) {
    if (v.size() == 3) {
        backtracking2();
        return;
    }
    for (int i = 0; i < 4 * n; i++) {
        if (choosenMaterial[i / 4]) continue;
        choosenMaterial[i / 4] = 1;
        v.push_back(i);
        backtracking1();
        v.pop_back();
        choosenMaterial[i / 4] = 0;
    }
}
 
int main(void) {
    ios::sync_with_stdio(false);
    cin.tie(0); cout.tie(0);
 
    cin >> n;
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < 4; j++)
            for (int k = 0; k < 4; k++)
                cin >> effect[4 * i][j][k];
        for (int j = 0; j < 4; j++)
            for (int k = 0; k < 4; k++)
                cin >> color[4 * i][j][k];
        turnClockwise(4 * i, 0);
    }
 
    backtracking1();
    cout << ans << '\n';
    return 0;
}

---