https://www.acmicpc.net/problem/15898
15898번: 피아의 아틀리에 ~신비한 대회의 연금술사~
"피아의 아틀리에 ~신비한 대회의 연금술사~"는 가난한 연금술사 피아의 성장스토리를 담은 게임이다. 이 게임의 가장 중요한 부분은 "대회"인데, 연금술로 높은 품질의 물건을 만들어 상금을 타
www.acmicpc.net
코드설명
Simulation(시뮬레이션) + Normal Permutation (일반순열) + Brute Force(완전탐색) 를 활용하는 문제입니다.
문제에서 유의해야할점들에 대해 먼저 정리하겠습니다.
1. 각 재료를 넣는 순서를 고려해야하고, 재료는 각 4가지 방향으로 회전함을 고려해야한다. ( 어떤 재료를 먼저 넣느냐에 따라서 마지막의 가마색깔이 변경될 수 있기에 위의 조건을 지켜야합니다. 처음에는 조합으로 구했기에 가마에 넣는 재료의 순서가 항상 고정되어있었고, 재료의 회전을 진행하지 않고 주어진 재료로만 진행했었습니다. )
2. 서로 다른 재료를 같은 칸에 여러번 넣어도 된다.
3. 문제에서 주어진 계산식을 활용하여 계산한다.
위의 3가지를 유의해야합니다.
간략하게 코드의 흐름은 다음과 같습니다.
- simulate: 재귀적으로 모든 재료의 배치 경우를 시뮬레이션하며 최적의 점수를 찾습니다.
- coloring: 재료를 게임 보드에 배치하고 색상을 적용합니다.
- calculateScore: 현재 게임 보드에 대한 점수를 계산합니다.
먼저, 시간복잡도에 관해 이야기해보겠습니다.
- 문제 조건에 주어진 재료 중 3개를 고른 뒤, 순서를 정해 가마에 잘 넣어야 한다.
문제를 보면 재료 개수 N개에서 반드시 3개를 선택하여야 합니다.
즉, 먼저 10P3 을 통해서 10 * 9 * 3 개의 숫자를 선택합니다.
저는 문제에 주어진 예시로 들어보면 4P3으로 예시를 보여드리겠습니다.
1 2 3 4 중에서 3개의 순열을 선택할시,
0 1 2
0 1 3
0 2 1
0 2 3
0 3 1
0 3 2
1 0 2
1 0 3
1 2 0
1 2 3
1 3 0
1 3 2
[생략]
...
....
로 총 24가지 선택됩니다.
이 상황에서 각 자리에 배치되는 경우의 수를 고려합니다.
각 재료가 Map[0][0], Map[0][1], Map[1][0], Map[1][1] 에 놓일 수 있으므로 총 4가지 격자에 놓을 수 있습니다.
즉, 4 가 곱해집니다.
문제에 주어진 조건에 의하여 재료는 시계방향으로 총 4번 회전될 수 있습니다.
[0],[1],[2],[3] 이 총 회전하는 Index를 의미한다고 가정합니다.
1 [0] 2[0] 3[0]
1 [0] 2[0] 3[1]
...
...
또다시 4가 곱해집니다.
즉, 시간복잡도를 보면,
4 * 3 * 2 * ( 4 * 4 ) ^ 3 입니다.
이떄 왜 ^3이 일어나는 이유는 총 3가지 재료가 4x4로 배치되기에 그렇습니다.
처음에 풀엇을대는 시간초과가 났었습니다.
이유는, 순열을 구한뒤 다시 한번 순서를 구하기에 시간초과가 발생했습니다.
처음 코드는 최하단에 위치해있습니다.
시간초과를 피하기 위해서는,
10P3 을 구하는 코드와 Map에 각 재료를 배치하는 방법을 동시에 진행해야합니다.
코드
시간초과를 해결한 코드입니다.
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;
public class Main {
public static int N, M, K = 0;
public static int[][] gama;
public static int[][] gamaColor;
public static int[][][][] map;
public static int[][][][] mapColor;
public static boolean[] visited;
public static int answer = 0;
public static void main(String[] args) throws IOException{
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st = new StringTokenizer(br.readLine());
N = Integer.parseInt(st.nextToken());
map = new int[10][4][4][4];
mapColor = new int[10][4][4][4];
visited = new boolean[10];
for(int t=0;t<N;t++) {
int[][] storeMap = new int[4][4];
for(int i=0;i<4;i++) {
st = new StringTokenizer(br.readLine());
for(int j=0;j<4;j++) {
storeMap[i][j] = Integer.parseInt(st.nextToken());
}
}
map[t][0] = storeMap;
for(int rotate = 1; rotate<4; rotate++) {
map[t][rotate] = rotate(map[t][rotate-1]);
}
storeMap = new int[4][4];
for(int i=0;i<4;i++) {
st = new StringTokenizer(br.readLine());
for(int j=0;j<4;j++) {
storeMap[i][j] = st.nextToken().charAt(0) - 'A';
}
}
mapColor[t][0] = storeMap;
for(int rotate = 1; rotate<4; rotate++) {
mapColor[t][rotate] = rotate(mapColor[t][rotate-1]);
}
}
gama = new int[5][5];
gamaColor = new int[5][5];
simulate(0);
System.out.println(answer);
}
public static void simulate(int level) {
if(level == 3) {
answer = Math.max(answer, calculateScore());
return ;
}
for(int i=0;i<N;i++) {
if(visited[i] == false) {
visited[i] = true;
int[][] storeGama = new int[5][5];
int[][] storeGamaColor = new int[5][5];
for(int r=0;r<5;r++) {
for(int c=0;c<5;c++) {
storeGama[r][c] = gama[r][c];
storeGamaColor[r][c] = gamaColor[r][c];
}
}
for(int r=0;r<2;r++) {
for(int c=0;c<2;c++) {
for(int rotate=0;rotate<4;rotate++) {
coloring(i, r, c, rotate);
simulate(level + 1);
for(int k=0;k<5;k++) {
for(int h=0;h<5;h++) {
gama[k][h] = storeGama[k][h];
gamaColor[k][h] = storeGamaColor[k][h];
}
}
}
}
}
visited[i] = false;
}
}
}
// R, B, G, Y, W는 재료의 순서에 따라서 값은 같아질 수 있지만, 색깔이 마지막에 저장되므로 순서가 중요하다.
public static int calculateScore() {
int score = 0;
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++) {
int color = gamaColor[i][j];
int sum = gama[i][j];
if(color == 'R' - 'A') {
R += sum;
}else if(color == 'B' - 'A') {
B += sum;
}else if(color == 'G' - 'A') {
G += sum;
}else if(color == 'Y' - 'A') {
Y += sum;
}else if(color == 'W' - 'A') { //아무것도 더하지 않습니다.
}
}
}
return R*7 + B*5 + G*3 + Y*2;
}
public static void coloring(int kindIndex, int startRow, int startCol, int rotateIndex) {
for(int k=0;k<4;k++) {
for(int h=0;h<4;h++) {
gama[startRow + k][startCol + h] += map[kindIndex][rotateIndex][k][h];
if(gama[startRow + k][startCol + h] < 0) {
gama[startRow + k][startCol + h] = 0;
} else if(gama[startRow + k][startCol + h] > 9) {
gama[startRow + k][startCol + h] = 9;
}
if(mapColor[kindIndex][rotateIndex][k][h] != 'W' - 'A') {
gamaColor[startRow + k][startCol + h] = mapColor[kindIndex][rotateIndex][k][h];
}
}
}
}
public static int[][] rotate(int[][] map) {
int[][] newMap = new int[4][4];
for(int i=0;i<4;i++) {
for(int j=0;j<4;j++) {
newMap[j][3-i] = map[i][j];
}
}
return newMap;
}
}
객체지향적으로 설계해본코드입니다.
폭탄의 품질을 구할때 R += (가마의 효능)을 했어야했는데 R+=1 로 처리하여 오류가 있었습니다.
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.LinkedList;
import java.util.Queue;
import java.util.StringTokenizer;
public class Main {
public static int N;
public static int answer = 0;
public static Ingredient[][] ingredientArr;
public static boolean[] permVisited;
public static Gama gama = new Gama();
public static void main(String[] args) throws IOException{
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st = new StringTokenizer(br.readLine());
N = Integer.parseInt(st.nextToken());
ingredientArr = new Ingredient[N][4];
permVisited = new boolean[N];
for(int kind = 0; kind < N; kind ++) {
ingredientArr[kind][0] = new Ingredient();
for(int row=0;row<4;row++) {
st = new StringTokenizer(br.readLine());
for(int col=0;col<4;col++) {
int input = Integer.parseInt(st.nextToken());
ingredientArr[kind][0].quality[row][col] = input;
}
}
for(int row=0;row<4;row++) {
st = new StringTokenizer(br.readLine());
for(int col=0;col<4;col++) {
char input = st.nextToken().charAt(0);
ingredientArr[kind][0].kind[row][col] = input;
}
}
for(int dir =1 ; dir < 4; dir++) {
ingredientArr[kind][dir] = rotateBy90Degree(ingredientArr[kind][dir - 1]);
}
}
simulate(0);
System.out.println(answer);
}
public static void simulate(int level) {
if(level == 3) { //재료를 3개 선택했다면, 폭탄의 품질을 계산합니다.
int R = 0, B = 0, G = 0, Y = 0, W = 0;
for(int i=0;i<5;i++) {
for(int j=0; j<5; j++) {
if(gama.kind[i][j] == 'R') {
R += gama.quality[i][j]; //처음에 단순히 1 을 더했다가 틀렸습니다. 가마의 효능만큼 더해주어야합니다.
}else if(gama.kind[i][j] == 'B') {
B += gama.quality[i][j];
}else if(gama.kind[i][j] == 'G') {
G += gama.quality[i][j];
}else if(gama.kind[i][j] == 'Y') {
Y += gama.quality[i][j];
}else if(gama.kind[i][j] == 'W') {
W += gama.quality[i][j];
}
}
}
int bombResult = 7 * R + 5 * B + 3 * G + 2 * Y + 0 * W;
answer = Math.max(answer, bombResult);
return ;
}
//가마 현재 값 저장
Gama storeGama = new Gama();
for(int i=0;i<5;i++) {
for(int j=0; j<5; j++) {
storeGama.quality[i][j] = gama.quality[i][j];
storeGama.kind[i][j] = gama.kind[i][j];
}
}
//재료를 넣는 순서를 고려해서 짜야한다.
for(int i=0;i<N;i++) {
if(permVisited[i] == false) {
permVisited[i] = true;
//선택한 재료를 5x5 격자 모양에서 넣을 수 있는 위치는 정해져있음을 알 수 있다.
for(int row=0; row < 2; row++) {
for(int col=0; col < 2; col++) {
//재료를 가마에 넣습니다. 이떄 회전 4방향까지 신경씁니다.
for(int dir = 0; dir < 4; dir++) {
putIngredient(i, dir, row, col);
//재귀함수 들어갑니다.
simulate(level + 1);
//다시 가마를 원상복구 시킵니다.
for(int k=0;k<5;k++) {
for(int h=0; h<5; h++) {
gama.quality[k][h] = storeGama.quality[k][h];
gama.kind[k][h] = storeGama.kind[k][h];
}
}
}
}
}
permVisited[i] = false;
}
}
}
public static void putIngredient(int ingredientIdx, int dirIdx, int startR, int startC) {
for(int row=startR; row < startR + 4; row++) {
for(int col = startC; col < startC + 4; col++) {
int qualityResult = gama.quality[row][col] + ingredientArr[ingredientIdx][dirIdx].quality[row - startR][col - startC];
if(qualityResult < 0) qualityResult = 0;
else if(qualityResult > 9) qualityResult = 9;
gama.quality[row][col] = qualityResult;
char kindResult = ingredientArr[ingredientIdx][dirIdx].kind[row - startR][col - startC];
if(kindResult != 'W') {
gama.kind[row][col] = kindResult;
}
}
}
}
public static Ingredient rotateBy90Degree(Ingredient ingredient) {
Ingredient temp = new Ingredient();
for(int r = 0; r < 4; r++) {
for(int c = 0; c < 4; c++) {
temp.quality[c][4 - r - 1] = ingredient.quality[r][c];
temp.kind[c][4 - r - 1] = ingredient.kind[r][c];
}
}
return temp;
}
}
class Ingredient{
int[][] quality = new int[4][4];
char[][] kind = new char[4][4];
public Ingredient() {
}
}
class Gama{
int[][] quality = new int[5][5];
char[][] kind = new char[5][5];
public Gama() {
for(int i=0;i<5;i++) {
for(int j=0;j<5;j++) {
this.kind[i][j] = 'W';
}
}
}
}
처음에 시간초과 난 코드입니다.
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.LinkedList;
import java.util.Map;
import java.util.Queue;
import java.util.StringTokenizer;
public class Main {
public static int N, M, K = 0;
public static int[][] gama;
public static int[][] gamaColor;
public static int[][][][] map;
public static int[][][][] mapColor;
public static int[][] orderMap;
public static boolean[] visited;
public static boolean[] coloringDFSVisited = new boolean[4];
public static int[] path = new int[N];
public static int[] pathRow = new int[N];
public static int[] pathCol = new int[N];
public static int answer = 0;
public static void main(String[] args) throws IOException{
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st = new StringTokenizer(br.readLine());
N = Integer.parseInt(st.nextToken());
map = new int[26][4][4][4];
mapColor = new int[26][4][4][4];
visited = new boolean[N * N];
orderMap = new int[2][2];
path = new int[N];
pathRow = new int[N];
pathCol = new int[N];
for(int t=0;t<N;t++) {
int[][] storeMap = new int[4][4];
for(int i=0;i<4;i++) {
st = new StringTokenizer(br.readLine());
for(int j=0;j<4;j++) {
storeMap[i][j] = Integer.parseInt(st.nextToken());
}
}
map[t][0] = storeMap;
for(int rotate = 1; rotate<4; rotate++) {
map[t][rotate] = rotate(map[t][rotate-1]);
}
storeMap = new int[4][4];
for(int i=0;i<4;i++) {
st = new StringTokenizer(br.readLine());
for(int j=0;j<4;j++) {
storeMap[i][j] = st.nextToken().charAt(0) - 'A';
}
}
mapColor[t][0] = storeMap;
for(int rotate = 1; rotate<4; rotate++) {
mapColor[t][rotate] = rotate(mapColor[t][rotate-1]);
}
}
for(int i=0;i<2;i++) {
Arrays.fill(orderMap[i], -1);
}
Arrays.fill(path, -1);
Arrays.fill(pathRow, -1);
Arrays.fill(pathCol, -1);
simulate(0, 0, 0, 0);
System.out.println(answer);
}
public static void simulate(int level, int nowR, int nowC, int putInside) {
if(nowC >= 2) {
nowR += 1; nowC = 0;
}
if(putInside == 3) {
//각 순서별로 로직이 정해졌으니, 그에 맞게 효능을 더해주고, 원소, 가마의 원소를 바꿔준다.
gama = new int[5][5];
gamaColor = new int[5][5];
for(int i=0;i<5;i++) {
Arrays.fill(gamaColor[i], 'W' - 'A');
}
coloringDFSVisited = new boolean[4];
Arrays.fill(path, -1);
Arrays.fill(pathRow, -1);
Arrays.fill(pathCol, -1);
coloringDFS(0, 0, 0, 0);
return ;
}
if(nowR >=2) {
return ;
}
for(int i=0;i<N*N;i++) {
if(visited[i/N] == false) {
visited[i/N] = true;
orderMap[nowR][nowC] = i;
simulate(level + 1, nowR, nowC + 1, putInside + 1);
orderMap[nowR][nowC] = -1;
visited[i/N] = false;
}
}
simulate(level + 1, nowR, nowC + 1, putInside);
}
public static void coloringDFS(int level, int nowR, int nowC, int coloredCnt) {
if(nowC >= 2) {
nowR += 1;
nowC = 0;
}
if(coloredCnt == 3) {
gama = new int[5][5];
gamaColor = new int[5][5];
coloring();
answer = Math.max(answer, calculateScore());
return ;
}
if(nowR >= 2) {
return ;
}
if(orderMap[level/2][level%2]!= -1){
for(int dir = 0; dir < 4; dir ++) {
if(orderMap[dir/2][dir%2] != -1 && coloringDFSVisited[dir] == false) {
coloringDFSVisited[dir] = true;
path[level] = orderMap[dir/2][dir%2];
pathRow[level] = dir/2;
pathCol[level] = dir%2;
coloringDFS(level + 1, nowR, nowC + 1, coloredCnt + 1);
// path[level] = -1;
coloringDFSVisited[dir] = false;
}
}
}
coloringDFS(level + 1, nowR, nowC + 1, coloredCnt);
}
// 내가 틀렸던 이유는 다음과 같다. 순서를 고려하지 못햇다.
// R, B, G, Y, W는 재료의 순서에 따라서 값은 같아질 수 있지만, 색깔이 마지막에 저장되므로 순서가 중요하다.
public static int calculateScore() {
int score = 0;
for(int i=0;i<5;i++) {
for(int j=0;j<5;j++) {
int color = gamaColor[i][j];
int sum = gama[i][j];
if(color == 'R' - 'A') {
sum *= 7;
}else if(color == 'B' - 'A') {
sum *= 5;
}else if(color == 'G' - 'A') {
sum *= 3;
}else if(color == 'Y' - 'A') {
sum *= 2;
}else if(color == 'W' - 'A') { //아무것도 더하지 않습니다.
sum *= 0;
}
score += sum;
}
}
if(score == 674) {
System.out.println("find!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!");
for(int i=0;i<2;i++) {
for(int j=0;j<2;j++) {
System.out.print(" "+orderMap[i][j]);
}
System.out.println();
}
System.out.println("=======");
for(int i=0;i<5;i++) {
for(int j=0;j<5;j++) {
int color = gamaColor[i][j];
System.out.print(" "+gama[i][j] +""+ (char)(color + 'A'));
}
System.out.println();
}
System.out.println("sum:"+score);
}
return score;
}
public static void coloring() {
for(int dir =0 ; dir < 4; dir++) {
int index = path[dir];
int startRow = pathRow[dir];
int startCol = pathCol[dir];
if(index == -1) continue;
int kindIndex = index / 4;
int rotateIndex = index % 4;
for(int k=0;k<4;k++) {
for(int h=0;h<4;h++) {
gama[startRow + k][startCol + h] += map[kindIndex][rotateIndex][k][h];
if(gama[startRow + k][startCol + h] < 0) {
gama[startRow + k][startCol + h] = 0;
} else if(gama[startRow + k][startCol + h] > 9) {
gama[startRow + k][startCol + h] = 9;
}
if(mapColor[kindIndex][rotateIndex][k][h] != 'W' - 'A') {
gamaColor[startRow + k][startCol + h] = mapColor[kindIndex][rotateIndex][k][h];
}
}
}
}
}
public static int[][] rotate(int[][] map) {
int[][] newMap = new int[4][4];
for(int i=0;i<4;i++) {
for(int j=0;j<4;j++) {
newMap[j][3-i] = map[i][j];
}
}
return newMap;
}
}