삼성 2024 상반기 오전 1번 문제 : 고대 문명 유적 탐사 [JAVA]

문제 링크

성공 여부(걸린 시간): 성공(2시간 22분 40초)

아이디어

크게 함수는 turn(돌리기), gainFirst(탐색), gainSecond(채우고 돌리고 반복) 3개로 나눠서 생각했다.

1단계
중심축이 될 후보는 9개
각 9개에서 3개의 각도로 돌릴수 있음
총 27개의 돌리고 나서의

• 유적지의 중심
• 돌린 각도(t가 1이면 90 2면 180 3이면 270)
• 돌렸을때의 유물 1차 획득 가치
• 돌리고 나서의 map(유물이 출토된 부분은 0으로 채움)
  이 정보들을 ancient class로 저장하고 우선순위큐로 정렬했다.
  (중심의 위치가 i, j라고 했을때 비교는 문제에서 준대로 가치-> 회전각도 -> j-> i로 정렬함)

여기서 가치는 높은 순대로 구현해야 하기에 어떻게 할지 고민해보았는데 reverse메소드는 오류가 나서
가치에 -1을 곱해서 음수로 두면 원본의 내림차순이 되어 동일한 동작을 할것이라 생각해 그렇게 해주었다.

근데 문제 🤔 돌리는건 어떻게 하지?

돌리는건 3X3배열에서 중앙을 제외한 8개의 칸만 시계방향으로 90도 돌려주는 함수 하나만 구현해주면
재사용하여 180도, 270도도 가능하다. 그런데 이걸 어떻게 구현할까?
난 단순하게 새로운 배열을 하나씩 만들고
돌렸을때의 값을 채워넣는 방식으로 진행하였다.

중심점과 1,1의 차이점값을 비교하여 좌표를 계산해주고
그 차이를 아래의 배열에 더해주면 원본 좌표와 그 좌표가 이동할 좌표가 나오게 된다.

before = {{0,0},{0,1},{0,2},{1,2},{2,2},{2,1},{2,0},{1,0}}
after = {{0,2},{1,2},{2,2},{2,1},{0,2},{1,0},{0,0},{0,1}}

그렇게 새로운 배열이 만들어졌다면 1차 유물가치 획득 함수(gainFirst)로 보내준다.

1차 유물획득의 로직은 한칸씩 돌면서 같은 숫자가 3개이상이라면 가치에 + 되고 해당 칸들은 0으로

초기화됨과 동시에 사이즈만큼 score 추가를 하게 되고
그리고 해당 중심점의 각도 버전에서 전부 다 돌았으면

ancient에 값(중심점 위치, 각도, 점수, 배열)을 넣고 pq에 넣어주고 return해줌.

2 단계

2차 유물획득(gainSecond)에 있어선 빈 벽채우기 + 새로 탐색해서 유물 찾기로 진행했다.
선정된 배열에 빈칸(0)을 유적의 벽면에 써있는 숫자가 저장된 큐에서 뽑아서 채운다.
그다음 다시 한칸씩 BFS탐색을 하며 1차 유물획득의 로직과 비슷하게 유물을 찾고 점수를 추가하는 동작을 한다.
이 행위를 더이상 3개의 유물이 연결되지 않을때 까지 반복하는데
해당 반복에서의 점수가 변동이 없으면 종료해주는 것으로 한다.

그리고 위의 총 행위를 K번을 반복함.
또한 모든 탐사가 끝났음에도 해당 턴에 대한 결과(thisTurnScore)가 0이라면

해당턴은 출력하지 않고 이전까지의 결과만 출력하고 끝냄

정답 코드

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

public class Main {
    static class ancient{
        int x, y, score, degree;
        int [][] map;
        public ancient(int x, int y, int score, int degree, int[][] map){
            this.x = x;
            this.y = y;
            this.score = score;
            this.degree = degree;
            this.map = map;
        }
    }
    static ArrayDeque<Integer> newNum;
    static PriorityQueue<ancient> pq;
    static int [][] originMap;
    public static void main(String[] args) throws IOException{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        newNum = new ArrayDeque<>();
        int K = Integer.parseInt(st.nextToken());
        int M = Integer.parseInt(st.nextToken());
        originMap = new int[5][5];
        for(int i=0; i<5; i++){
            StringTokenizer input = new StringTokenizer(br.readLine());
            for(int j=0; j<5; j++){
                int num = Integer.parseInt(input.nextToken());
                originMap[i][j] = num;
            }
        }
        StringTokenizer ms = new StringTokenizer(br.readLine());
        for(int i=0; i<M; i++){
            newNum.add(Integer.parseInt(ms.nextToken()));
        }
        StringBuilder sb = new StringBuilder();
        outer:
        for(int round=0; round<K; round++){
            pq = new PriorityQueue<ancient>(Comparator.comparingInt((ancient o1)->(o1.score*-1))
            .thenComparingInt(o1->o1.degree)
            .thenComparingInt(o1->o1.y)
            .thenComparingInt(o1->o1.x));
            //유적지 중심 별로 돌려보고 ancient 생성해서 pq에 넣기
            for(int i = 1; i <= 3; i++){
                for(int j = 1; j <= 3; j++){
                    int [][] temp = deepCopy(originMap);
                    for(int t = 1; t<=3; t++){
                        temp = turn(i, j, temp);//90도씩 돌림
                        gainFirst(i, j, temp, t);
                    }
                }
            }
            int thisTurnScore = 0;
            ancient cur = pq.poll();
            thisTurnScore+=cur.score;
            originMap = cur.map;
            // 이제 채워주고 탐색하기 반복
            while(true){
                //채워주기
                boolean flag = false;
                for(int j=0; j<5; j++){
                    for(int i=4; i>=0; i--){
                        if(originMap[i][j]==0){
                            originMap[i][j] = newNum.poll();
                            //채워줄곳없으면 종료하는거 탐지하려고
                            flag = true;
                        }
                    }
                }
                if(!flag){
                    break;
                }
                //탐색하기
                int addScore = gainSecond();
                if(addScore==0){
                    break;
                }
                else{
                    thisTurnScore+=addScore;
                }
            }
            if(thisTurnScore==0){
                break outer; 
            }
            else{ 
                sb.append(thisTurnScore+" ");
            }
        }
        if(sb.length()!=0){
            sb.setLength(sb.length()-1);
        }
        System.out.print(sb);
    }
    static int[][] deepCopy(int [][] arr){
        int [][] temp = new int [5][5];
        for(int i=0; i<5; i++){
            for(int j=0;j<5; j++){
                temp[i][j] = arr[i][j];
            }
        }
        return temp;
    }
    static int [][] before = {{0,0},{0,1},{0,2},{1,2},{2,2},{2,1},{2,0},{1,0}};
    static int [][] after = {{0,2},{1,2},{2,2},{2,1},{2,0},{1,0},{0,0},{0,1}};
    static int [][] turn(int centerX, int centerY, int [][] arr){
        int [][] turnArr = deepCopy(arr);
        int gapX = centerX-1;//중심과의 행차이
        int gapY = centerY-1;//중심과의 열차이
        for(int i=0; i<8; i++){
            int originX = gapX + before[i][0];
            int originY = gapY + before[i][1];
            int turnX = gapX + after[i][0];
            int turnY = gapY + after[i][1];
            turnArr[turnX][turnY] = arr[originX][originY];
        }
        return turnArr;
    }
    static int [] dx = {1, 0, -1, 0};
    static int [] dy = {0, 1, 0, -1};
    static void gainFirst(int centerX, int centerY, int[][] arr, int t){
        int [][] findArr = deepCopy(arr);
        int score=0;
        boolean [][] visited = new boolean[5][5];
        for(int i=0; i<5; i++){
            for(int j=0; j<5; j++){
                if(!visited[i][j]&&findArr[i][j]!=0){
                    int target = findArr[i][j];
                    ArrayDeque<int[]> q = new ArrayDeque<>();
                    ArrayList<int[]> remove = new ArrayList<>();
                    q.add(new int[]{i, j});
                    remove.add(new int[]{i, j});
                    visited[i][j] = true;
                    while(!q.isEmpty()){
                        int [] cur = q.poll();
                        int x = cur[0];
                        int y = cur[1];
                        for(int dir = 0; dir<4; dir++){
                            int mx = x+dx[dir];
                            int my = y+dy[dir];
                            if(canGo(mx, my)&&!visited[mx][my]&&findArr[mx][my]==target){
                                remove.add(new int []{mx, my});
                                q.add(new int []{mx, my});
                                visited[mx][my] = true;
                            }
                        }
                    }
                    if(remove.size()>=3){
                        score+= remove.size();
                        for(int [] rm : remove){
                            findArr[rm[0]][rm[1]] = 0;
                        }
                    }
                }
            }
        }
        pq.add(new ancient(centerX, centerY, score, t, findArr));
    }
    static int gainSecond(){// originMap으로 하면됨
        int score=0;
        boolean [][] visited = new boolean[5][5];
        for(int i=0; i<5; i++){
            for(int j=0; j<5; j++){
                if(originMap[i][j]!=0){
                    int target = originMap[i][j];
                    ArrayDeque<int[]> q = new ArrayDeque<>();
                    ArrayList<int[]> remove = new ArrayList<>();
                    q.add(new int[]{i, j});
                    remove.add(new int[]{i, j});
                    visited[i][j] = true;
                    while(!q.isEmpty()){
                        int [] cur = q.poll();
                        int x = cur[0];
                        int y = cur[1];
                        for(int dir = 0; dir<4; dir++){
                            int mx = x+dx[dir];
                            int my = y+dy[dir];
                            if(canGo(mx, my)&&!visited[mx][my]&&originMap[mx][my]==target){
                                remove.add(new int []{mx, my});
                                q.add(new int []{mx, my});
                                visited[mx][my] = true;
                            }
                        }
                    }
                    if(remove.size()>=3){
                        score+= remove.size();
                        for(int [] rm : remove){
                            originMap[rm[0]][rm[1]] = 0;
                        }
                    }
                }
            }
        }
        return score;
    }
    static boolean canGo(int x, int y){
        return x>=0&&y>=0&&x<5&&y<5;
    }
}