이번에 풀어본 문제는
백준 21609번 상어 중학교 입니다.

📕 문제 링크

❗️코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;

class Block
{
    int x,y,r_cnt,size;
    String points;

    public Block(int x, int y, int r_cnt,int size,String points)
    {
        this.x = x;
        this.y = y;
        this.r_cnt = r_cnt;
        this.size = size;
        this.points = points;
    }
    public Block(int x, int y)
    {
        this.x = x;
        this.y = y;
    }

}
public class Main {
    static final int BLANK = 6;
    static int N, M,answer;
    static boolean [][] visited;
    static int[][] map;
    static int [] dx = {-1,1,0,0};
    static int [] dy = {0,0,-1,1};
    static PriorityQueue<Block> pq;

    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());
        M = Integer.parseInt(st.nextToken());
        if(N == 1)
        {
            System.out.print("0");
            return;
        }
        map = new int[N][N];
        pq = new PriorityQueue<>(new Comparator<Block>() {
            @Override
            public int compare(Block o1, Block o2) {
                if (o1.size == o2.size) {
                    if (o1.r_cnt == o2.r_cnt) {
                        if (o1.x == o2.x) return o2.y - o1.y;
                        return o2.x - o1.x;
                    }
                    return o2.r_cnt - o1.r_cnt;
                }
                return o2.size - o1.size;
            }
        });

        for (int i = 0; i < N; ++i) {
            st = new StringTokenizer(br.readLine());
            for (int j = 0; j < N; ++j) {
                map[i][j] = Integer.parseInt(st.nextToken());
            }
        }
        find();
        while(!pq.isEmpty())
        {
            Block cur = pq.poll();
            st = new StringTokenizer(cur.points);
            while(st.hasMoreTokens())
            {
                int x = Integer.parseInt(st.nextToken());
                int y = Integer.parseInt(st.nextToken());
                map[x][y] = BLANK;
            }
            answer += (cur.size * cur.size);

            gravity();
            rotate();
            gravity();
            pq.clear();
            find();
        }
        System.out.print(answer);
    }
    static void find()
    {
        visited = new boolean[N][N];
        for (int i = 0; i < N; ++i)
        {
            for(int j = 0; j < N; ++j)
            {
                if(!visited[i][j])
                {
                    if(map[i][j] > 0 && map[i][j] <= M)
                    {
                        visited[i][j] = true;
                        makeBlock(i,j);
                    }
                }
            }
        }
    }
    static void makeBlock(int x, int y) // 무지개블록은 공통으로 사용할 수 있으므로 방문배열을 돌려놔야함
    {
        int size = 1;
        int r_cnt = 0;
        int color = map[x][y];
        StringBuilder sb = new StringBuilder(x+" "+y);
        StringBuilder rainbow = new StringBuilder();
        Queue<Block> q = new LinkedList<>();
        q.add(new Block(x,y,0,0,""));

        while(!q.isEmpty())
        {
            Block cur = q.poll();
            for(int dir = 0; dir < 4; ++dir)
            {
                int mx = cur.x + dx[dir];
                int my = cur.y + dy[dir];

                if(!isValid(mx,my) || visited[mx][my] || map[mx][my] == BLANK) continue;
                if(map[mx][my] == 0)
                {
                    q.add(new Block(mx,my));
                    rainbow.append(mx+" "+my+" ");
                    r_cnt++;
                }
                else if(map[mx][my] == color) q.add(new Block(mx,my));
                else continue;
                visited[mx][my] = true;
                size++;
                sb.append(" "+mx+" "+my);
            }
            if(q.isEmpty())
            {
                if(size >= 2)
                {
                    pq.add(new Block(x,y,r_cnt,size,sb.toString()));
                    if(r_cnt > 0)
                    {
                        StringTokenizer st = new StringTokenizer(rainbow.toString());
                        while(st.hasMoreTokens())
                        {
                            int fst = Integer.parseInt(st.nextToken());
                            int sec = Integer.parseInt(st.nextToken());
                            visited[fst][sec] = false;
                        }
                    }
                }
            }
        }

    }
    static void gravity()
    {
        for(int i = 0; i < N; ++i)
        {
            for(int j = N-1; j >= 0; --j)
            {
                if(map[j][i] == BLANK || map[j][i] == -1) continue;
                int dest = j+1;
                while(true)
                {
                    if(dest == N) break;
                    if(map[dest][i] == BLANK) dest++;
                    else break;
                }
                if(dest == j+1) continue;
                map[dest-1][i] = map[j][i];
                map[j][i] = BLANK;
            }
        }
    }
    static void rotate()
    {
        int [][] tmp = new int[N][N];
        for(int i = 0; i < N; ++i)
        {
            for(int j = 0; j < N; ++j)
            {
                tmp[N-j-1][i] = map[i][j];
            }
        }
        for(int i = 0; i < N; ++i)
        {
            System.arraycopy(tmp[i],0,map[i],0,N);
        }
    }
    static boolean isValid(int x, int y)
    {
        return x >= 0 && y >= 0 && x < N && y < N;
    }
}

📝 풀이

구현 문제입니다.
먼저 주어진 조건에 맞게 map에서 그룹을 묶어줍니다. 이 때, 무지개 블록은 블록의 색상에 관계없이 모두 포함될 수 있으므로 방문배열을 다시 초기화 시켜주어야 합니다.
묶어준 그룹 중 크기, 무지개블록 갯수, 행,열의 크기 순으로 우선순위를 정하여 가장 큰 그룹을 제거시켜주고 중력, 회전, 중력 순으로 map을 변경시켜줍니다.
앞선 과정을 계속 반복 수행하여, 남은 그룹이 없을 경우 종료합니다.

📜 후기

무지개 블록에 대한 방문배열이 공통으로 사용된다는것을 인지하지 못해서 틀렸었습니다. 무지개블록에 대한 방문배열을 공유하게 되면, 앞선 그룹에서 끌어다 쓴 무지개블록을 다른 그룹에서는 활용할 수 없기 때문에 무지개블록에 대한 방문배열을 공유하면 안됩니다. 따라서 그룹화 과정에서 사용된 무지개블록의 좌표값을 기록해 둔 후 방문배열을 다시 false로 변경해주어 해결했습니다.
해결은 했지만, 코드가 조금 길다고 생각해서 시간 남을 때 다른 해결방법도 참고해 볼 생각입니다.
(문제추천 - 노형)