[백준] 21609: 상어 중학교 [Java]

 

알고리즘 분류: 구현, 시뮬레이션

문제 링크: https://www.acmicpc.net/problem/21609

 

---

 

구현이 은근히 쉽지 않았던 문제.

 

일단 문제는 그냥 주어진 로직을 순서대로 구현하면 된다.

필요 로직은 다음과 같다.

 

1. 그룹핑

2. 그룹 중 가장 블록 개수가 많은 그룹 없애기(-2 로 설정했음) 

3. 이때 그룹들의 블록 개수가 모두 2 미만이라면 종료

4. 블록 개수의 제곱만큼 점수를 더한다.

5. 블록 내리기

6. 왼쪽으로 90도 회전

7. 블록 내리기

8. 1번으로 다시 돌아간다.

 

이때 주의할 점은

그룹핑 할 때는 무지개 블록을 기준으로는 하면 안된다는 점,

기준 블록은 무조건 그룹핑을 시작한 블록 기준이라는 점(그래서 그냥 배열을 순서대로 순회하면 된다)

그룹핑 하고 나서는 무지개 블록은 방문 처리를 다시 false로 해주어야 한다는 점이다.

 

무지개 블록을 다시 방문 처리 false로 해주는 이유는 무지개 블록은 어떤 그룹에도 속할 수 있기 때문이다.

 

그리고 각 블록 그룹의 정보를 저장하는 Info 클래스를 정의해주었다.

그룹에 포함된 블록의 좌표 목록(removeList), 무지개 블록의 수(rainbow), 그룹의 기준 블록의 좌표(y, x)를 저장해서 한 사이클에 돌 때 제거해야 할 그룹을 지정하기 쉽게끔 만들어주었다.

 

---

 

 

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;
import java.util.Queue;
import java.util.StringTokenizer;

class Main {
    static class Info{
        List<int[]>removeList;
        int rainbow;
        int y,x;
        Info(List<int[]> removeList,int rainbow,int y,int x){
            this.removeList=removeList;
            this.rainbow=rainbow;
            this.y=y;this.x=x;
        }
    }

    static int[] dy= {-1,1,0,0};
    static int[] dx= {0,0,-1,1};
    static BufferedReader br=new BufferedReader(new InputStreamReader(System.in));
    static StringTokenizer st;
    static int[][] arr;
    static int n,m;

    public static void main(String[] args) throws IOException {
        st=new StringTokenizer(br.readLine());
        n=Integer.parseInt(st.nextToken());
        m=Integer.parseInt(st.nextToken());
        arr=new int[n][n];
        for(int i=0;i<n;i++) {
            st=new StringTokenizer(br.readLine());
            for(int j=0;j<n;j++) {
                arr[i][j]=Integer.parseInt(st.nextToken());
            }
        }
        int total=0;
        while(true) {
            Info removeInfo=new Info(new ArrayList<>(),0,0,0);
            boolean[][] visited=new boolean[n][n];

            for(int i=0;i<n;i++) {
                for(int j=0;j<n;j++) {
                    if(arr[i][j]>0&&!visited[i][j]) {
                        visited[i][j]=true;
                        Info newInfo=bfs(i,j,arr[i][j],visited);

                        if(newInfo.removeList.size()<2) continue;

                        if(removeInfo.removeList.size()<newInfo.removeList.size()) {
                            removeInfo=newInfo;
                        }else if(removeInfo.removeList.size()==newInfo.removeList.size()){
                            if(removeInfo.rainbow<newInfo.rainbow){
                                removeInfo=newInfo;
                            }else if(removeInfo.rainbow==newInfo.rainbow){
                                if(removeInfo.y<newInfo.y){
                                    removeInfo=newInfo;
                                }else if(removeInfo.y==newInfo.y){
                                    if(removeInfo.x<newInfo.x){
                                        removeInfo=newInfo;
                                    }
                                }
                            }
                        }
                    }
                }
            }

            List<int[]> removeList=removeInfo.removeList;
            if(removeList.isEmpty())break;

            int size=removeList.size();
            total+=size*size;

            for(int[] pos:removeList) arr[pos[0]][pos[1]]=-2;

            down();
            rotate();
            down();
        }
        System.out.println(total);
    }

    private static void rotate() {
        int[][] temp=new int[n][n];
        for(int i=0;i<n;i++){
            for(int j=0;j<n;j++){
                temp[n-j-1][i]=arr[i][j];
            }
        }
        arr=temp;
    }

    private static void down() {
        for(int j=0;j<n;j++){
            for(int i=n-2;i>=0;i--){
                if(arr[i][j]>=0){
                    int y=i;
                    while(y+1 < n && arr[y+1][j] == -2){
                        arr[y+1][j] = arr[y][j];
                        arr[y][j] = -2;
                        y++;
                    }
                }
            }
        }
    }

    private static Info bfs(int i,int j,int num,boolean[][] visited) {
        List<int[]> rainbowList=new ArrayList<>();
        List<int[]> removeList=new ArrayList<>();
        removeList.add(new int[]{i,j});

        Queue<int[]>q=new LinkedList<>();
        q.add(new int[] {i,j});

        while(!q.isEmpty()) {
            int[] pos=q.poll();
            int y=pos[0];
            int x=pos[1];
            for(int d=0;d<4;d++) {
                int ny=y+dy[d];
                int nx=x+dx[d];

                if(ny<0||nx<0||ny>=n||nx>=n)continue;
                if(visited[ny][nx])continue;

                if(arr[ny][nx]==num||arr[ny][nx]==0){
                    if(arr[ny][nx]==0){
                        rainbowList.add(new int[]{ny, nx});
                    }
                    visited[ny][nx]=true;
                    q.add(new int[] {ny,nx});
                    removeList.add(new int[] {ny,nx});
                }
            }
        }
        for(int[] pos:rainbowList){
            visited[pos[0]][pos[1]]=false;
        }
        return new Info(removeList,rainbowList.size(),i,j);
    }
}