[boj] 백준 21609 상어 중학교 (Java) - 시뮬레이션, BFS

[문제]

https://www.acmicpc.net/problem/21609

21609번: 상어 중학교

 

[풀이]

1. 블록 그룹을 구한다. 인접해있고, 같은 색의 일반 블록과 무지개 블록으로 구성되어있으며 검은 블록은 포함되면 안된다. BFS를 돌려서 구할 수 있다. 정렬에 필요한 데이터들을 저장해주었다. 중요한 점은 무지개 블록은 중복되어 포함될 수 있다!! 대놓고 써져있지 않아서 처음에 이 부분을 간과했는데 "무지개 블록은 얼마나 들어있든 상관없다." 는 부분을 주의해야 한다. 이를 위해서 BFS를 돌린 후 무지개 블록에 대해서는 visited 배열을 다시 원상태로 돌려줘야 한다. 또한 일반블록이 무조건 하나 이상 포함되어야 블록 그룹에 들어갈 수 있으므로 일반블록을 시작점으로 BFS를 돌렸다. 이외에도 포함 블록의 개수가 2 이상이 안되면 블록 그룹에 들어갈 수 없으므로 visited 배열을 false로 바꿔주고, 기준 블록 선정 시 무지개 블록은 안된다는 조건 등 여러 조건을 문제를 보고 잘 확인해야 한다.

2. 블록 그룹을 기준에 따라 정렬한다. 

3. 가장 첫번째 블록 그룹의 전체 개수 제곱만큼 점수를 획득한다.

4. 중력을 적용한다. 행이 큰 방향으로 이동하는데 검은 블록은 이동하지 않는다. n-2 행부터 0행까지 이동시켜준다. 범위를 벗어나거나 다른 블록을 만나기 전까지 행 인덱스를 증가시켜가며 이동 가능한 행을 찾는다.

5. 반시계 방향으로 90도 회전한다.

6. 다시 중력이 적용된다.

7. 블록그룹을 다시 구한다. 블록 그룹이 존재하는 동안 위 과정을 반복한다.

 

[코드]

 

package 시뮬레이션;
import java.util.*;
import java.io.*;

public class boj_21609_java {
    static int n, m;
    static int[][] board;
    static int score;
    static boolean[][] visited;
    static int[] dr = {1, -1, 0, 0};
    static int[] dc = {0, 0, 1, -1};
    public static class Group{
        int cnt; //전체 블록 개수
        int rainbowCnt; //무지개색 블록 개수
        int r, c; //기준 블록 행, 열
        List<int[]> blocks = new ArrayList<>();

        Group(int cnt, int rainbowCnt, int r, int c, List<int[]> blocks){
            this.cnt = cnt;
            this.rainbowCnt = rainbowCnt;
            this.r = r;
            this.c = c;
            this.blocks = blocks;
        }
    }
    public static void main(String[] args) throws Exception{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());

        n = Integer.parseInt(st.nextToken());
        m = Integer.parseInt(st.nextToken());

        board = new int[n][n];
        for(int i=0; i<n; i++){
            st = new StringTokenizer(br.readLine());
            for(int j=0; j<n; j++){
                board[i][j] = Integer.parseInt(st.nextToken());
            }
        }

        //-1 검정블럭, 0 무지개 블럭, 1~m 색상

        //인접해 있고, 검은 블록은 포함하지 않는 모든 같은 색 블록들 그룹에 추가 
        List<Group> list = new ArrayList<>();
        getBlockGroup(list);


        //블록 그룹이 존재하는동안 반복
        while(list.size()>0){
            //블록 그룹 정렬. 전체 블록 개수, 무지개 블록 개수, 기준 블록 행, 열 내림차순
            list.sort(new Comparator<Group>(){
                @Override
                public int compare(Group g1, Group g2){
                    if(g1.cnt==g2.cnt){
                        if(g1.rainbowCnt==g2.rainbowCnt){
                            if(g1.r==g2.r){
                                return Integer.compare(g2.c, g1.c);
                            }
                            else return Integer.compare(g2.r, g1.r);
                        }
                        else return Integer.compare(g2.rainbowCnt, g1.rainbowCnt);
                    }
                    else return Integer.compare(g2.cnt, g1.cnt);
                }
            });

            //블록그룹의 모든 블록 제거, b^2 점수 획득
            score += list.get(0).cnt*list.get(0).cnt;
            for(int[] b : list.get(0).blocks){
                board[b[0]][b[1]] = -2; //블록 제거 의미 
            }

            //격자에 중력 작용
            gravity();

            //격자 90도 반시계방향 회전
            rotate();

            //격자에 중력 작용
            gravity();

            //블록 그룹 구하기
            list = new ArrayList<>();
            getBlockGroup(list);
        }

        System.out.println(score);

    }

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

        board = temp;
    }

    public static void gravity(){
        //행이 큰 방향으로 이동
        for(int i=n-2; i>=0; i--){
            for(int j=0; j<n; j++){
                if(board[i][j]==-1 || board[i][j]==-2) continue; //검은 블록은 이동 안함, 블록 없는 경우
                
                //범위 벗어나기 전, 다른 블록 만나기 전까지 이동
                int idx = i+1;
                while(idx<n && board[idx][j]==-2){
                    idx++;
                }

                if(idx-1!=i){ //블록이 이동 한 경우
                    board[idx-1][j] = board[i][j];
                    board[i][j] = -2; //블록 이동해서 제거됨.
                }
            }
        }

    }

    public static void getBlockGroup(List<Group> list){
        visited = new boolean[n][n];
        for(int i=0; i<n; i++){
            for(int j=0; j<n; j++){
                if(visited[i][j] || board[i][j]==-1 || board[i][j]==0 || board[i][j]==-2) continue;
                bfs(i, j, list);
            } 
        }
    }

    public static void bfs(int r, int c, List<Group> list){
        Queue<int[]> q = new LinkedList<>();
        List<int[]> blocks = new ArrayList<>();
        List<int[]> rainbowBlocks = new ArrayList<>();

        q.add(new int[]{r, c});
        visited[r][c] = true;

        int rainbowCnt = 0; //무지개 블록
        int generalCnt = 1; //일반블록
        
        int color = board[r][c];

        blocks.add(new int[]{r, c});

        while(!q.isEmpty()){
            int[] p = q.poll();

            for(int i=0; i<4; i++){
                int nr = p[0] + dr[i];
                int nc = p[1] + dc[i];

                //범위 밖이거나 블록이 없거나 검은 블록
                if(nr<0 || nc<0 || nr>=n || nc>=n || board[nr][nc]==-1 || visited[nr][nc] || board[nr][nc]==-2) continue;

                //무지개색이 아닌데 다른 색이면 패스
                if(board[nr][nc]!=0 && board[nr][nc]!=color) continue;

                visited[nr][nc] = true;
                if(board[nr][nc]==0) {
                    rainbowBlocks.add(new int[]{nr, nc});
                    rainbowCnt++;
                }
                else generalCnt++;

                blocks.add(new int[]{nr, nc});
                q.add(new int[]{nr, nc});
            }
        }

        if(blocks.size()<2) {
            //방문 표시 해제
            for(int[] b:blocks){
                visited[b[0]][b[1]] = false;
            }
            return;
        }

        //무지개 블록 방문 원상복구
        for(int[] b:rainbowBlocks){
            visited[b[0]][b[1]] = false;
        }
        

        //기준 블록 찾기. 일반블록 중 행번호 오름차순, 열번호 오름차순.
        blocks.sort(new Comparator<int[]>() {
            @Override
            public int compare(int[] o1, int[] o2) {
                if(o1[0]==o2[0]){
                    return Integer.compare(o1[1], o2[1]);
                }
                else return Integer.compare(o1[0], o2[0]);
            }
        });

        int standardR = 0, standardC = 0;
        for(int[] b:blocks){
            if(board[b[0]][b[1]]==0) continue;
            standardR = b[0];
            standardC = b[1];
            break;
        }
        
        list.add(new Group(rainbowCnt+generalCnt, rainbowCnt, standardR, standardC, blocks));
        
    }
    
 }