소프티어

보시기 편하게 문제 링크 입니다

https://softeer.ai/practice/info.do?eventIdx=1&psProblemId=540

먼저 저는 java로 풀었습니다

최적화를 위해서 여러가지 생각을 해 봤는데요...

1. 2차원 배열 말고 linked list 배열을 사용해서 넣고 빼기 쉽게 했습니다. (ArrayList도 해봤는데 시간초과..)
2. dfs를 쓸 때 배열을 copy하지 않고 필요한 부분만 뺐다 넣었다 했습니다.

3. 한 라운드에서 얻을 수 있는 최대값을 구해놓고(N*N*2) 최대로 더하는 경우에도 Max보다 작다면 그 경우는 실행하지 않도록 했습니다.

4. 삭제되는 블럭들의 위치 최대, 최소값을 minX, minY, maxX, maxY 에 넣어놓고 사용해서 반복문의 횟수를 줄였습니다.

5. 3번째 단계에서는 블럭 삭제하는 연산을 하지 않고 세기만 했습니다 + 만약 최고 점수(N*N*2*3 이라면 아예 끝내도록 했습니다)

이 외에도 어떤 걸 더 해야 할까요..?

+) 추가로 visited는 현재 삭제할 블럭들을 선택하기 위한 배열이고

localV는 전에 선택한 블럭을 이전에 고려했던 블럭을 다시 고려하지 않기 위한 배열입니다.

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


public class Main
{
    static int N;
    static int[] dx = {-1,1,0,0};
    static int[] dy = {0,0,-1,+1};
    static boolean[][][] visited;
    static int Max;
    static int roundMax;
    static  LinkedList[] arr;
    public static void main(String args[]) throws Exception
    {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        
        N = Integer.parseInt(br.readLine());
        int[][] map = new int[3*N][N];
        for(int i = 0; i<3*N; i++){
            StringTokenizer st = new StringTokenizer(br.readLine());
            for(int j = 0; j();
            for(int i = 3*N-1; i>=0; i--){
                arr[j].add(map[i][j]);
            }
        }
        roundMax = N*N*2; // 단계별로 얻을 수 있는 최대 점수
        visited = new boolean[3][3*N][N];
        Max = 0;
        dfs(0,0);
        System.out.println(Max);
    }

    private static void dfs(int cnt, int score){
        if(cnt == 0 && score+roundMax*3<=Max){ 
            return;
        }
        if(cnt == 1 && score+roundMax*2<=Max){
            return;
        }
        if(cnt == 2 && score+roundMax<=Max){
            return;
        }

        boolean[][] localV = new boolean[3*N][N];
        for(int i = 0; i q = new LinkedList();
                q.add(new Data(i,j));
                int num = arr[i].get(j);
                int minX = i;
                int minY = j;
                int maxX = i;
                int maxY = j;
                while(!q.isEmpty()){
                    Data data = q.poll();
                    int x = data.x;
                    int y = data.y;

                    for(int d=0; d<4; d++){
                        int nx = x+dx[d];
                        int ny = y+dy[d];

                        if(nx<0||ny<0||nx>=N||ny>=arr[nx].size()||ny>=N||localV[ny][nx]){ // 범위 벗어났거나 방문했으면
                            continue;
                        }

                        if(arr[i].get(j) != arr[nx].get(ny)){
                            continue;
                        }

                        localV[ny][nx] = true;
                        visited[cnt][ny][nx] = true;

                        q.add(new Data(nx,ny));
                        minX = Math.min(minX,nx);
                        minY = Math.min(minY,ny);
                        maxX = Math.max(maxX,nx);
                        maxY = Math.max(maxY,ny);
                    }
                }

                int count = 0;

                if(cnt == 2){
                    for(int m = minX; m<=maxX; m++){
                        for(int n = maxY; n>=minY; n--){
                            if(visited[cnt][n][m]){
                                count++;
                            }
                        }
                    }
                    Max = Math.max(score + (maxX-minX+1)*(maxY-minY+1) + count,Max);
                    if(Max == roundMax*3){
                        System.out.println(Max);
                        System.exit(0);
                    }
                } else {
                    Stack stack = new Stack<>();
                    for(int m = minX; m<=maxX; m++){
                        for(int n = maxY; n>=minY; n--){
                            if(visited[cnt][n][m]){
                                stack.push(new Data(m,n));
                                arr[m].remove(n);
                                count++;
                            }
                        }
                    }

                    dfs(cnt+1, score + (maxX-minX+1)*(maxY-minY+1) + count);
                    
                    while(stack.size()!=0){
                        Data data = stack.pop();
                        arr[data.x].add(data.y, num);
                    }
                }
            }
        }
    }
    private static class Data{
        int x;
        int y;

        Data(int x, int y){
            this.x = x;
            this.y = y;
        }
    }
}