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

15898번 피아의 아틀리에 ~신비한 대회의 연금술사~

 

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

 

문제

"피아의 아틀리에 ~신비한 대회의 연금술사~"는 가난한 연금술사 피아의 성장스토리를 담은 게임이다. 이 게임의 가장 중요한 부분은 "대회"인데, 연금술로 높은 품질의 물건을 만들어 상금을 타야만 피아가 먹고 살 수 있기 때문이다. 스토리는 매우 길지만 여백이 없어 생략하기로 하고, 여러분은 이 게임의 대회 기능을 확인해달라는 요청을 받았다. 여러분이 확인해야 하는 대회는 다음과 같다.

여러분은 5×5 격자 모양 가마에 서로 다른 재료 3개를 순서대로 넣어 최고 품질의 폭탄을 만들어야 한다. 재료는 대회에서 준비해주며, 넣을 수 있는 재료의 후보는 10개 이하이다. 주어진 재료 중 3개를 고른 뒤, 순서를 정해 가마에 잘 넣어야 한다.

가마의 각 칸에는 품질을 나타내는 숫자와 원소를 나타내는 색이 칠해져 있다. 초기에는 모든 칸의 품질은 0, 원소는 흰색이다. 재료는 4×4 모양으로 생겼으며, 재료의 i행 j열에는 2가지 정보가 있다.

1. 효능: 가마 한 칸의 품질을 바꾸는 -9 이상 9 이하의 정수 xi,j
2. 원소: 가마 한 칸의 원소를 바꿀 수 있는 색 ci,j (빨강 'R', 파랑 'B', 초록 'G', 노랑 'Y', 흰색 'W' 중 하나이다)

재료를 가마에 넣을 때는 5×5 격자를 벗어날 수 없다. 회전은 가능하나, 격자에 맞지 않게 기울여 넣을 수는 없다. 재료를 가마에 넣을 때, 가마의 상태는 다음과 같이 바뀐다.

1. 재료가 위치하지 않는 가마의 격자칸은 아무런 변화가 생기지 않는다.

2. 재료가 위치한 가마의 격자칸에 있는 품질과 원소값은 바뀔 수 있다.

   • 격자의 품질은 재료의 효능이 더해진다. 더한 뒤의 값이 음수인 경우 0으로, 9 초과인 경우 9로 바뀐다.
   • 격자의 색은 재료의 원소가 흰색인 경우 그대로, 아닌 경우 재료의 원소와 같은 색으로 칠해진다.

재료 3개를 모두 넣어야만 폭탄이 만들어지며, 폭탄의 품질은 다음과 같이 계산된다. 가마의 최종 상태에서 빨강, 파랑, 초록, 노랑으로 칠해진 부분의 품질 합을 각각 R, B, G, Y라고 했을 때,

(폭탄의 품질) = 7R + 5B + 3G + 2Y

폭탄을 만들기 위한 재료의 후보가 주어졌을 때, 재료를 적절히 선택하고 배치하여 만들 수 있는 폭탄의 최대 품질을 구하자.

 

입력

첫 번째 줄에 재료의 개수를 나타내는 자연수 n이 주어진다. (3 ≤ n ≤ 10)

두 번째 줄부터 n개의 재료 정보가 순서대로 주어진다. 각 재료의 정보는 다음과 같다. 먼저 4개의 줄에 효능을 나타내는 수 4개가 공백을 사이에 두고 주어진다. 다음 4개의 줄에 원소를 나타내는 글자 4개가 공백을 사이에 두고 주어진다. 이 글자는 R, B, G, Y, W 중 하나임이 보장된다.

 

출력

첫 번째 줄에 품질의 최댓값을 출력한다.

 

예제 입력

4
6 3 3 -9
-6 8 -6 8
9 5 1 -1
-8 2 -3 -1
R B G Y
Y B R R
W R R R
G R W B
-6 -2 -4 -3
1 -3 0 9
8 -7 2 0
0 3 -5 7
W B R Y
Y W R B
W B G G
Y G B R
8 7 2 1
-9 8 8 -9
-1 -4 8 6
-7 8 -3 8
Y W W G
Y B R B
Y W R R
R Y W Y
4 -5 8 3
2 3 1 3
-5 0 1 -3
4 3 3 -6
W Y G W
G G R W
G Y G R
R R G Y

 

예제 출력

634

 

해결방법

DFS + 백트래킹을 통해 모든 경우를 다해보는 완전 탐색 문제이다

해설 : UCPC 2018 온라인 예선 문제 해설

 

 

⭐️ 솔루션 ⭐️

완전탐색 유형의 문제이다

최대 10개의 재료 중 3개를 선택 (순서 상관O) 할 수 있다 (𝚗Ｐ𝚛)

또한 각 재료는 (0,0) ~ (1,1) 까지 4개의 좌표에 놓을 수 있으며 4가지 방향을 가지고 있다

따라서 (10x9x8) x (4x4)^3 = 2,949,120 이므로 모든 경우를 해볼 수 있다 !!

 

 

전체적인 흐름은 아래와 같다

1. 각 재료의 효능과 원소를 입력받은 뒤, 90도 회전을 총 3번 수행하여 각 상태를 저장한다
2. 각 재료를 모두 돌며 재료를 배치시킨다
3. 이 때, 재료를 배치하는 경우는 [시작좌표인 (0,0) (0,1) (1,0) (1,1) 에 재료를 배치하는 경우] x [4방향 회전시킨 자료를 배치하는 경우] 총 16가지가 존재한다
4. 재귀함수를 통해 총 3개의 재료를 배치하였으면 폭탄의 최대 품질을 구해 최대값을 갱신시켜준다

 

 

 

소스코드

문제 해결 시간 : 1h 20m

메모리 : 1996 KB

시간 : 2416 ms

#include <iostream>
#include <cstring>
#include <math.h>
#include <vector>
#include <algorithm>
#define INF 987654321
using namespace std;

struct state {
    int eff;
    char ele;
    
    state() { }
    state(int _eff,char _ele) : eff(_eff),ele(_ele) { }
};

int n,ans;
int efficacy[10][4][4][4];
char element[10][4][4][4];
bool visited[10];

vector<vector<state>> map(5,vector<state>(5));

// 입력 배열을 90도로 3번 회전하여 각각을 저장하는 함수
void rotateArr(int type,int dir){
    // 90 도 회전
    for(int i=0; i<4; i++){
        for(int j=0; j<4; j++){
            efficacy[type][dir][i][j] = efficacy[type][dir-1][3-j][i];
            element[type][dir][i][j] = element[type][dir-1][3-j][i];
        }
    }
}

// 폭탄의 최대 품질을 구하는 함수
int getQuality(vector<vector<state>> v){
    int r = 0;
    int b = 0;
    int g = 0;
    int y = 0;
    
    for(int i=0; i<5; i++){
        for(int j=0; j<5; j++){
            switch (v[i][j].ele) {
                case 'R':
                    r += v[i][j].eff;
                    break;
                case 'B':
                    b += v[i][j].eff;
                    break;
                case 'G':
                    g += v[i][j].eff;
                    break;
                case 'Y':
                    y += v[i][j].eff;
                    break;
                default:
                    break;
            }
        }
    }
    
    return 7*r + 5*b + 3*g + 2*y;
}

// 가마에 재료의 종류, 방향에 따라 재료를 놓는 함수
vector<vector<state>> putMaterial(vector<vector<state>> v,int row,int col,int type,int dir){
    for(int i=0; i<4; i++){
        for(int j=0; j<4; j++){
            // 효능
            v[row+i][col+j].eff += efficacy[type][dir][i][j];
            
            if(v[row+i][col+j].eff < 0)
                v[row+i][col+j].eff = 0;
            else if(v[row+i][col+j].eff > 9)
                v[row+i][col+j].eff = 9;
            
            // 원소
            if(element[type][dir][i][j] != 'W'){
                v[row+i][col+j].ele = element[type][dir][i][j];
            }
        }
    }
    
    return v;
}

void dfs(vector<vector<state>> v,int cnt){
    // 재료 3개를 모두 선택한 경우
    if(cnt == 3){
        ans = max(ans,getQuality(v));
        return;
    }
    
    // dfs
    for(int t=0; t<n; t++){
        if(!visited[t]){
            visited[t] = true;
            
            // (0,0) (0,1) (1,0) (1,1)
            // 4 좌표에 대해 재료 배치 가능
            for(int i=0; i<=1; i++){
                for(int j=0; j<=1; j++){
                    // 원래방향, 시계방향, 반시계방향
                    for(int d=0; d<4; d++){
                        vector<vector<state>> tmp = putMaterial(v,i,j,t,d);
                        
                        dfs(tmp,cnt+1);
                    }
                }
            }
            
            visited[t] = false;
        }
    }
}

int main(int argc, const char * argv[]) {
    // cin,cout 속도향상
    ios_base::sync_with_stdio(false);
    cin.tie(NULL); cout.tie(NULL);
    
    cin >> n;
    for(int t=0; t<n; t++){
        // 효능 입력
        for(int i=0; i<4; i++){
            for(int j=0; j<4; j++){
                cin >> efficacy[t][0][i][j];
            }
        }
        
        // 원소 입력
        for(int i=0; i<4; i++){
            for(int j=0; j<4; j++){
                cin >> element[t][0][i][j];
            }
        }
        
        // 입력받은 효능, 원소 회전
        for(int d=1; d<=3; d++){
            rotateArr(t,d);
        }
    }
    
    // 초기화
    for(int i=0; i<5; i++){
        for(int j=0; j<5; j++){
            map[i][j] = state(0,'W');
        }
    }
    memset(visited, false, sizeof(visited));
    ans = -INF;
    
    dfs(map,0);
    
    cout << ans << "\n";
    
    return 0;
}