[백준] 15898 피아의 아틀리에 ~신비한 대회의 연금술사~ - Simulation(시뮬레이션) + Normal Permutation (일반순열) + Brute Force(완전탐색) JAVA

passionfruit200 2023. 12. 21. 11:54

2023. 12. 21. 11:54

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

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

"피아의 아틀리에 ~신비한 대회의 연금술사~"는 가난한 연금술사 피아의 성장스토리를 담은 게임이다. 이 게임의 가장 중요한 부분은 "대회"인데, 연금술로 높은 품질의 물건을 만들어 상금을 타

www.acmicpc.net

코드설명

Simulation(시뮬레이션) + Normal Permutation (일반순열) + Brute Force(완전탐색) 를 활용하는 문제입니다.

문제에서 유의해야할점들에 대해 먼저 정리하겠습니다.

1. 각 재료를 넣는 순서를 고려해야하고, 재료는 각 4가지 방향으로 회전함을 고려해야한다. ( 어떤 재료를 먼저 넣느냐에 따라서 마지막의 가마색깔이 변경될 수 있기에 위의 조건을 지켜야합니다. 처음에는 조합으로 구했기에 가마에 넣는 재료의 순서가 항상 고정되어있었고, 재료의 회전을 진행하지 않고 주어진 재료로만 진행했었습니다. )

2. 서로 다른 재료를 같은 칸에 여러번 넣어도 된다.

3. 문제에서 주어진 계산식을 활용하여 계산한다.

위의 3가지를 유의해야합니다.

간략하게 코드의 흐름은 다음과 같습니다.

simulate: 재귀적으로 모든 재료의 배치 경우를 시뮬레이션하며 최적의 점수를 찾습니다.
1. coloring: 재료를 게임 보드에 배치하고 색상을 적용합니다.
2. 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;
    }
}

'알고리즘 > 백준' 카테고리의 다른 글

[백준] 15683 감시 - Brute Force(완전탐색) + 구현(Implementation) + Simulation(시뮬레이션) JAVA (0)	2024.01.07
[백준] 14500 테트로미노 - 구현(Implementation) + Simulation(시뮬레이션) + Brute Force(완전탐색) JAVA (0)	2024.01.05
[백준] 16986 인싸들의 가위바위보 - Simulation(시뮬레이션) + Normal Permutation (일반순열) JAVA (0)	2023.12.20
[백준] 11559 Puyo Puyo - Simulation(시뮬레이션) + BFS(너비우선탐색) JAVA (0)	2023.12.20
[백준] 15655 N과 M (6) - 백트래킹(BackTracking) JAVA (0)	2023.12.19

내 블로그 - 관리자 홈 전환	`Q` `Q`
새 글 쓰기	`W` `W`

글 수정 (권한 있는 경우)	`E` `E`
댓글 영역으로 이동	`C` `C`

이 페이지의 URL 복사	`S` `S`
맨 위로 이동	`T` `T`
티스토리 홈 이동	`H` `H`
단축키 안내	`Shift` + `/` `⇧` + `/`

passionfruit200