본문 바로가기
알고리즘 풀이/백준

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

by 2245 2023. 6. 30.

🔗문제

 

👨🏻‍💻 풀이 및 코드

문제 유형 및 난이도 : 구현, 브루트 포스 / G1

 

1. Point 클래스 생성

  • 재료를 회전할 수 있기 때문에, score, color 배열을 따로 만든다면 각각을 회전 시켜야 한다.
  • 한번에 넣어 회전시키기 위해 Class 를 생성했다.
static class Point {
    int score;
    char color;

    Point(int score, char color) {
        this.score = score;
        this.color = color;
    }
}

 

2. N개 중에 3개를 뽑아 나열한다. -> 순열

  • N개 중에 이미 뽑은 재료는 건너뛴다.
  • selection에는 넣어야 할 재료의 번호와 순서를 저장한다. ex) 2, 1, 3
  • 3개의 재료를 모두 뽑았다면, 가마의 상태를 초기화하고 재료를 하나씩 넣는 과정을 진행한다.
static void perm(int cnt, boolean[] isSelected, int[] selection) {
    if(cnt==3) {
        //가마 상태 초기화
        Point[][] kiln = new Point[K][K];
        for(int a=0; a<K; a++) {
            for(int b=0; b<K; b++) {
                kiln[a][b] = new Point(0, 'W');
            }
        }
        process(selection, 0, kiln);
        return;
    }

    for(int i=0; i<N; i++) {
        if(isSelected[i]) continue;
        isSelected[i] = true;
        selection[cnt] = i; 

        perm(cnt+1, isSelected, selection);

        isSelected[i] = false;
    }
}

 

3. 재료 넣기

  • selection에 해당하는 재료를 순서대로 넣는다.
  • 재료는 왼쪽 상단이 (0,0), (0, 1), (1, 0), (1,1) 인 지점에 넣을 수 있고, 각각의 경우에 4방향으로 회전시킬 수 있다.
  • 모든 재료를 넣었다면, 합을 계산해 answer를 갱신한다.
// 가마에 넣기
static void process(int[] selection, int cnt, Point[][] oriKiln) {
    if(cnt == 3) {	// 다 넣음
        int[] score = new int[4];	//0:R, 1:B, 2:G, 3:Y

        for(int a=0; a<K; a++) {
            for(int b=0; b<K; b++) {
                if(oriKiln[a][b].color == 'W') continue;
                int idx = -1;
                switch(oriKiln[a][b].color) {
                    case 'R':
                        idx = 0;
                        break;
                    case 'B':
                        idx = 1;
                        break;
                    case 'G':
                        idx = 2;
                        break;
                    case 'Y':
                        idx = 3;
                        break;
                }
                score[idx]+=oriKiln[a][b].score;
            }
        }

        answer = Math.max(answer, 7*score[0]+5*score[1]+3*score[2]+2*score[3]);
        return;
    }

    int idx = selection[cnt];
    for(int i=0, size=K-M; i<=size; i++) {
        for(int j=0; j<=size; j++) {

            for(int d=0; d<4; d++) {		//4방향 회전
                turnRight(idx);

                //가마 복사
                Point[][] kiln = new Point[K][K];
                for(int a=0; a<K; a++) {
                    for(int b=0; b<K; b++) {
                        Point point = oriKiln[a][b];
                        kiln[a][b] = new Point(point.score, point.color);
                    }
                }

                //재료넣기
                for(int a=0; a<M; a++) {
                    for(int b=0; b<M; b++) {
                        int score = oriKiln[a+i][b+j].score + ingredients[idx][a][b].score;
                        if(score < 0) {
                            score = 0;
                        }
                        if(score > 9) {
                            score = 9;
                        }

                        kiln[a+i][b+j].score = score;
                        char color = ingredients[idx][a][b].color;
                        if(color == 'W') {
                            continue;
                        }
                        kiln[a+i][b+j].color = color;
                    }
                }

                process(selection, cnt+1, kiln);
            }
        }
    }
}
주의! 
Class Point와 같이 객체를 복사해 원본을 유지하고 싶을 때, 객체를 그대로 복사하면 주소 참조로 인해 원하는 복사가 이루어지지 않을 수 있다.  
ex) 
//가마 복사
Point[][] kiln = new Point[K][K];
for(int a=0; a<K; a++) {
    for(int b=0; b<K; b++) {
        kiln[a][b] = oriKiln[a][b];
    }
}​

kiln[a][b] = oriKiln[a][b] 로 작성하면 kiln[a][b]의 객체를 수정했을 때 oriKiln[a][b]의 값도 같이 수정된다. (주소 참조)

//가마 복사
Point[][] kiln = new Point[K][K];
for(int a=0; a<K; a++) {
    for(int b=0; b<K; b++) {
        Point point = oriKiln[a][b];
        kiln[a][b] = new Point(point.score, point.color);
    }
}​
new 생성자를 통해 새 객체를 생성하여 값을 복사하자!

 

 

전체 코드

import java.io.*;
import java.util.*;

public class Main_bj_15898_피아의아틀리에_sol2 {

	static int N, answer;		// 재료의 갯수
	static final int M = 4;		// 재료의 가로, 세로 길이
	static final int K = 5;		// 가마의 가로, 세로 길이
	static Point[][][] ingredients;
	
	public static void main(String[] args) throws Exception {
		System.setIn(new FileInputStream("res/input_bj_15898.txt"));
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		N = Integer.parseInt(br.readLine());
		ingredients = new Point[N][M][M];
		
		StringTokenizer st;
		for(int i=0; i<N; i++) {
			int[][] score = new int[M][M];
			
			for(int a=0; a<M; a++) {
				st = new StringTokenizer(br.readLine());
				for(int b=0; b<M; b++) {
					score[a][b] = Integer.parseInt(st.nextToken());
				}
			}
			
			for(int a=0; a<M; a++) {
				st = new StringTokenizer(br.readLine());
				for(int b=0; b<M; b++) {
					char color = st.nextToken().charAt(0);
					ingredients[i][a][b] = new Point(score[a][b], color);
				}
			}
		}
		//INPUT END
		
		//N개의 재료 중에 3개를 선택, 순열
		answer = 0;
		perm(0, new boolean[N], new int[3]);
		System.out.println(answer);
	}
	
	static void perm(int cnt, boolean[] isSelected, int[] selection) {
		if(cnt==3) {
			//가마 상태 초기화
			Point[][] kiln = new Point[K][K];
			for(int a=0; a<K; a++) {
				for(int b=0; b<K; b++) {
					kiln[a][b] = new Point(0, 'W');
				}
			}
			process(selection, 0, kiln);
			return;
		}
		
		for(int i=0; i<N; i++) {
			if(isSelected[i]) continue;
			isSelected[i] = true;
			selection[cnt] = i; 
			
			perm(cnt+1, isSelected, selection);
			
			isSelected[i] = false;
		}
	}
	
	// 가마에 넣기
	static void process(int[] selection, int cnt, Point[][] oriKiln) {
		if(cnt == 3) {	// 다 넣음
			int[] score = new int[4];	//0:R, 1:B, 2:G, 3:Y
			
			for(int a=0; a<K; a++) {
				for(int b=0; b<K; b++) {
					if(oriKiln[a][b].color == 'W') continue;
					int idx = -1;
					switch(oriKiln[a][b].color) {
						case 'R':
							idx = 0;
							break;
						case 'B':
							idx = 1;
							break;
						case 'G':
							idx = 2;
							break;
						case 'Y':
							idx = 3;
							break;
					}
					score[idx]+=oriKiln[a][b].score;
				}
			}
			
			answer = Math.max(answer, 7*score[0]+5*score[1]+3*score[2]+2*score[3]);
			return;
		}
		
		int idx = selection[cnt];
		for(int i=0, size=K-M; i<=size; i++) {
			for(int j=0; j<=size; j++) {
				
				for(int d=0; d<4; d++) {		//4방향 회전
					turnRight(idx);
					
					//가마 복사
					Point[][] kiln = new Point[K][K];
					for(int a=0; a<K; a++) {
						for(int b=0; b<K; b++) {
							Point point = oriKiln[a][b];
							kiln[a][b] = new Point(point.score, point.color);
						}
					}
					
					//재료넣기
					for(int a=0; a<M; a++) {
						for(int b=0; b<M; b++) {
							int score = oriKiln[a+i][b+j].score + ingredients[idx][a][b].score;
							if(score < 0) {
								score = 0;
							}
							if(score > 9) {
								score = 9;
							}
							
							kiln[a+i][b+j].score = score;
							char color = ingredients[idx][a][b].color;
							if(color == 'W') {
								continue;
							}
							kiln[a+i][b+j].color = color;
						}
					}
					
					process(selection, cnt+1, kiln);
				}
			}
		}
	}
	
	static Point[][] turnRight(int idx) {
		Point[][] tmp = new Point[M][M];
		for(int i=0; i<M; i++) {
			for(int j=0; j<M; j++) {
				tmp[i][j] = ingredients[idx][i][j];
			}
		}
		
		for(int i=0; i<M; i++) {
			for(int j=0; j<M; j++) {
				ingredients[idx][i][j] = tmp[M-j-1][i];
			}
		}
		
		return tmp;
	}
	
	static class Point {
		int score;
		char color;
		
		Point(int score, char color) {
			this.score = score;
			this.color = color;
		}
	}

}

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

[BOJ] 6987. 월드컵 - JAVA  (0) 2023.05.15
[BOJ] 17825. 주사위 윷놀이 - JAVA  (0) 2023.05.13
[BOJ] 23290. 마법사 상어와 복제 - JAVA  (0) 2023.04.24
[BOJ] 11660. 구간 합 구하기 5 - JAVA  (0) 2023.03.16
[BOJ] 10986. 나머지 합 - JAVA  (0) 2023.03.15

관련글

티스토리툴바