[ 백준 / BOJ 21609 ] 상어 중학교 ( 자바 / JAVA )

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

21609번: 상어 중학교

문제 설명

게임 NxN인 격자에서 진행, 초기에는 모든 칸에 블록이 하나씩 존재
블록 👉

• 검은색 블록 : -1
• 무지개 블록 : 0
• 일반 블록 : M가지 색상, 1 ~ M

블록 그룹 : 연결된 블록의 집합

• 일반 블록은 적어도 하나 존재
• 일반 블록은 모두 같은 색
• 검은색 블록은 존재 ❌
• 무지개 블록의 개수는 상관 ❌
• 블록의 개수 >= 2
• 기준 블록은 일반 블록 중에서 행 번호가 가장 작은 블록 → 열 번호가 가장 작은 블록

오토 플레이 기능

블록 그룹이 존재하는 동안 반복

1. 크기가 가장 큰 블록 그룹을 찾는다. 여러 개라면 👉
   1) 무지개 블록의 수가 가장 많은 그룹
   2) 기준 블록의 행이 가장 큰 것
   3) 기준 블록의 열이 가장 큰 것
2. 1에서 찾은 그룹의 블록을 모두 제거. $B^2$점을 획득(B → 블록의 개수)
3. 중력 작용 👉 검은색 블록을 제외한 모든 블록이 행의 번호가 큰 칸으로 이동, 다른 블록이나 격자의 경계를 만나기 전까지
4. 격자가 90도 반시계 방향으로 회전
5. 중력 작용

문제 풀이

Block 클래스

블록 그룹을 표시하는 클래스
총 블록의 개수(numOfTotal), 무지개 블록의 개수(numOfRainBow), 기준블록의 좌표(x, y)
비교 함수(compareTo)

@Override
public int compareTo(Block o) {
    if (this.numOfTotal == o.numOfTotal) {
        if (this.numOfRainBow == o.numOfRainBow) {
            if(this.x == o.x) return o.y - this.y;
            return o.x - this.x;
        }
        return o.numOfRainBow - this.numOfRainBow;
    }
    return o.numOfTotal - this.numOfTotal;
}

1. 블록 그룹들 찾기

gameMap[x][y]을 돌면서, 기본 블록이고 방문하지 않은 칸을 찾음
findBlockGroup(x,y,boolean)
boolean이 true라면 👉 모든 블록 그룹들을 찾는 것
boolean이 false 👉 2번에서 사용

BFS 진행,
조건에 맞는 블록을 찾으면 total += 1,
total >= 2라면, 블록 그룹 리스트에 추가!
flag 👉 true,
무지개 블록은 공통으로 사용될 수 있기 때문에, isVisited를 false로 변경

2. 조건에 맞는 블록그룹 내 블록 삭제

블록 그룹들의 리스트를 Sort 👉 맨 앞의 블록그룹(block) 선택
다시 findBlockGroup(block.x, block.y, false) 진행

그 후, removeBlock() 진행
앞의 findBlockGroup에서 isVisited가 true 값으로 변한 블록들을 BLANK = 6으로 값 바꿔줌
ans += Block.numOfTotal * Block.numOfTotal;

3. 중력 작용

gravity()

한 열씩 진행하면서, 일반 또는 무지개 블록의 밑의 행이 비어있으면 내려줌

4. 90도 반시계 회전

rotate()

끝 전체 열부터 0행부터 전체로 이동
tmp[i][j] = gameMap[j][N-i-1];

5. 다시 중력 작용

gravity()

이 것을 블록 그룹들이 발견되지 않을 때까지 진행.!!

코드

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

public class Main_BOJ_21609_상어_중학교 {

    static class Block implements Comparable<Block>{
        int numOfTotal, numOfRainBow, x, y;

        public Block(int numOfTotal, int numOfRainBow, int x, int y) {
            this.numOfTotal = numOfTotal;
            this.numOfRainBow = numOfRainBow;
            this.x = x;
            this.y = y;
        }

        @Override
        public int compareTo(Block o) {
            if (this.numOfTotal == o.numOfTotal) {
                if (this.numOfRainBow == o.numOfRainBow) {
                    if(this.x == o.x) return o.y - this.y;
                    return o.x - this.x;
                }
                return o.numOfRainBow - this.numOfRainBow;
            }
            return o.numOfTotal - this.numOfTotal;
        }
    }

    static int N, M, ans = 0;
    static final int BLACK = 6;
    static int[][] gameMap;
    static boolean[][] isVisited;
    static List<Block> blockGroup;
    static int[] dx = {-1, 0, 0, 1};
    static int[] dy = {0, -1, 1, 0};

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer stringTokenizer = new StringTokenizer(br.readLine());

        N = Integer.parseInt(stringTokenizer.nextToken());
        M = Integer.parseInt(stringTokenizer.nextToken());

        gameMap = new int[N][N];

        for (int i = 0; i < N; i++) {
            stringTokenizer = new StringTokenizer(br.readLine());
            for (int j = 0; j < N; j++) {
                gameMap[i][j] = Integer.parseInt(stringTokenizer.nextToken());
            }
        }

        while (true) {
            blockGroup = new ArrayList<>();
            isVisited = new boolean[N][N];
            for (int i = 0; i < N; i++) {
                for (int j = 0; j < N; j++) {
                    if(0 < gameMap[i][j] && gameMap[i][j] <= M && !isVisited[i][j]) findBlockGroup(i, j, true);
                }
            }
            if(blockGroup.isEmpty()) break;

            Collections.sort(blockGroup);
            isVisited = new boolean[N][N];
            findBlockGroup(blockGroup.get(0).x, blockGroup.get(0).y, false);
            removeBlock();
            ans += blockGroup.get(0).numOfTotal * blockGroup.get(0).numOfTotal;
            gravity();
            rotate();
            gravity();
        }

        System.out.println(ans);
    }

    private static void rotate() {
        int[][] tmp = new int[N][N];
        for (int i = 0; i < N; i++) {
            for (int j = 0; j < N; j++) {
                tmp[i][j] = gameMap[j][N - i - 1];
            }
        }

        for (int i = 0; i < N; i++) {
            System.arraycopy(tmp[i], 0, gameMap[i], 0, N);
        }
    }

    private static void gravity() {
        for (int j = 0; j < N; j++) {
            for (int i = N - 1; i >= 0; i--) {
                if(gameMap[i][j] == BLACK || gameMap[i][j] == -1) continue;
                int dest = i + 1;

                while (true) {
                    if(dest == N) break;
                    if(gameMap[dest][j] == BLACK) dest += 1;
                    else break;
                }
                if(dest == i+1) continue;
                gameMap[dest - 1][j] = gameMap[i][j];
                gameMap[i][j] = BLACK;
            }
        }
    }

    private static void removeBlock() {
        int cnt = 0;
        for (int i = 0; i < N; i++) {
            for (int j = 0; j < N; j++) {
                if(isVisited[i][j]){
                    cnt += 1;
                    gameMap[i][j] = BLACK;
                }
            }
        }
    }

    private static void findBlockGroup(int x, int y, boolean flag) {
        Queue<int[]> q = new LinkedList<>();
        int blockColor = gameMap[x][y];
        isVisited[x][y] = true;
        q.add(new int[]{x, y});

        int total = 1;
        int rainbow = 0;
        while (!q.isEmpty()) {
            int[] now = q.poll();

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

                if (nx < 0 || ny < 0 || N <= nx || N <= ny || isVisited[nx][ny]) continue;
                if (gameMap[nx][ny] != 0 && gameMap[nx][ny] != blockColor) continue;

                if (gameMap[nx][ny] == 0) rainbow += 1;
                total += 1;
                isVisited[nx][ny] = true;
                q.add(new int[]{nx, ny});
            }
        }

        if (total >= 2) blockGroup.add(new Block(total, rainbow, x, y));
        if (flag) {
            for (int i = 0; i < N; i++) {
                for (int j = 0; j < N; j++) {
                    if (gameMap[i][j] == 0) isVisited[i][j] = false;
                }
            }
        }
    }
}