백준 - 21609 상어 중학교(Java)

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

21609번: 상어 중학교

 

구현 문제입니다.

 

주어진 조건의 순서대로 구현을 해야 합니다.

1. 크기가 가장 큰 블록 그룹을 찾는다. 그러한 블록 그룹이 여러 개라면 포함된 무지개 블록의 수가 가장 많은 블록 그룹, 그러한 블록도 여러개라면 기준 블록의 행이 가장 큰 것을, 그 것도 여러개이면 열이 가장 큰 것을 찾는다.
2. 1에서 찾은 블록 그룹의 모든 블록을 제거한다. 블록 그룹에 포함된 블록의 수를 B라고 했을 때, B2점을 획득한다.
3. 격자에 중력이 작용한다.
4. 격자가 90도 반시계 방향으로 회전한다.
5. 다시 격자에 중력이 작용한다.

 

1번은 bfs를 통해 블록의 그룹을 구하면 됩니다. 주의해야 할 점은 무지개색 블록의 경우 모든 인접한 그룹 모두가 공유되기 때문에 방문을 계속 풀어줘야 합니다.

 

2번은 조건에 맞는 블록 그룹의 첫 번째를 제거하면 됩니다. (사이즈는 1번에서 구해 저장하면 됩니다.)

 

3~5번은 말 그대로 구현하면 됩니다.

 

계속 반복하면서 제거할 블록 그룹이 없을 경우 반복을 종료하면 됩니다.

 

[구현 코드]

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

public class Main {
    private static final int[] dx = {-1, 1, 0, 0};
    private static final int[] dy = {0, 0, -1, 1};
    private static final String SEPARATOR = " ";
    private static final int REMOVED_BLOCK = -2;
    private static final int BLACK = -1;

    private static int n, m;

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        StringTokenizer stz = new StringTokenizer(br.readLine(), SEPARATOR);

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

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

        int answer = 0;

        while (true) {
            boolean[][] visited = new boolean[n][n];
            List<BlockGroup> blockGroups = new ArrayList<>();

            // 해당 맵에서 무지개색 블록의 위치를 저장함
            List<int[]> rainbows = new ArrayList<>();
            for (int i = 0; i < n; i++) {
                for (int j = 0; j < n; j++) {
                    if (map[i][j] == 0) rainbows.add(new int[]{i, j});
                }
            }

            for (int i = 0; i < n; i++) {
                for (int j = 0; j < n; j++) {
                    if (!visited[i][j] && map[i][j] > 0) {

                        // 무지개색은 다른 블럭도 방문할 수 있도록 방문을 품
                        for (int x = 0; x < rainbows.size(); x++) {
                            visited[rainbows.get(x)[0]][rainbows.get(x)[1]] = false;
                        }

                        // bfs로 블록 그룹들의 정보를 구함
                        getBlockSize(map, visited, i, j, blockGroups);
                    }
                }
            }

            // 1. 크기가 가장 큰 블록 그룹을 찾는다.
            // 그러한 블록 그룹이 여러 개라면 포함된 무지개 블록의 수가 가장 많은 블록 그룹,
            // 그러한 블록도 여러개라면 기준 블록의 행이 가장 큰 것을, 그 것도 여러개이면 열이 가장 큰 것을 찾는다.
            Collections.sort(blockGroups);

            // 더 이상 제거할 블록이 없으면 반복 종료
            if (blockGroups.size() == 0) break;

            // 2. 1에서 찾은 블록 그룹의 모든 블록을 제거한다.
            // 블록 그룹에 포함된 블록의 수를 B라고 했을 때, B^2점을 획득한다.
            removeBlock(map, blockGroups.get(0));
            answer += (int) Math.pow(blockGroups.get(0).size, 2);

            // 3. 격자에 중력이 작용한다.
            gravity(map);

            // 4. 격자가 90도 반시계 방향으로 회전한다.
            map = rotateMap(map);

            // 5. 다시 격자에 중력이 작용한다.
            gravity(map);
        }

        bw.write(String.valueOf(answer));

        bw.flush();
        bw.close();
        br.close();
    }

    private static void gravity(int[][] map) {
        for (int j = 0; j < n; j++) {
            for (int i = n - 1; i >= 0; i--) {

                if (map[i][j] == REMOVED_BLOCK) {

                    for (int t = i - 1; t >= 0; t--) {
                        // 검은색은 내릴 수 없음
                        if (map[t][j] == BLACK) {
                            break;
                        }
                        // 위의 블록을 확인하여 내려 갈 수 있는 블록이 있으면 빈칸과 자리를 바꿔 내림
                        else if (map[t][j] >= 0) {
                            map[i][j] = map[t][j];
                            map[t][j] = REMOVED_BLOCK;
                            break;
                        }
                    }
                }
            }
        }
    }

    private static int[][] rotateMap(int[][] map) {
        int[][] rotated = new int[n][n];

        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                rotated[i][j] = map[j][n - i - 1];
            }
        }
        return rotated;
    }

    private static void removeBlock(int[][] map, BlockGroup blockGroup) {
        Queue<int[]> qu = new LinkedList<>();
        qu.add(new int[]{blockGroup.x, blockGroup.y});
        int color = map[blockGroup.x][blockGroup.y];
        map[blockGroup.x][blockGroup.y] = REMOVED_BLOCK;

        while (!qu.isEmpty()) {
            int[] cn = qu.poll();
            int cx = cn[0];
            int cy = cn[1];

            for (int i = 0; i < 4; i++) {
                int nx = cx + dx[i];
                int ny = cy + dy[i];

                if (!inRange(nx, ny)) continue;

                if (map[nx][ny] == 0 || map[nx][ny] == color) {
                    map[nx][ny] = REMOVED_BLOCK;
                    qu.add(new int[]{nx, ny});
                }
            }
        }
    }

    private static void getBlockSize(int[][] map, boolean[][] visited,
                                     int x, int y, List<BlockGroup> blockGroups) {
        Queue<int[]> qu = new LinkedList<>();
        qu.add(new int[]{x, y});
        visited[x][y] = true;
        int color = map[x][y];
        int rainbowCount = 0;

        int size = 0;

        while (!qu.isEmpty()) {
            int[] cn = qu.poll();
            int cx = cn[0];
            int cy = cn[1];

            size++;

            for (int i = 0; i < 4; i++) {
                int nx = cx + dx[i];
                int ny = cy + dy[i];

                if (!inRange(nx, ny) || visited[nx][ny]) continue;

                if (map[nx][ny] == 0 || map[nx][ny] == color) {
                    visited[nx][ny] = true;
                    qu.add(new int[]{nx, ny});

                    if (map[nx][ny] == 0) rainbowCount++;
                }
            }
        }

        // 크기가 2 이상인 것만 추가
        if (size > 1) {
            blockGroups.add(new BlockGroup(x, y, size, rainbowCount));
        }
    }

    private static boolean inRange(int x, int y) {
        return (x >= 0 && y >= 0 && x < n && y < n);
    }

    private static class BlockGroup implements Comparable<BlockGroup> {
        int x, y, size, rainBowCount;

        public BlockGroup(int x, int y, int size, int rainBowCount) {
            this.x = x;
            this.y = y;
            this.size = size;
            this.rainBowCount = rainBowCount;
        }

        // 조건에 맞춰 내림차순 블록 그룹 정렬
        @Override
        public int compareTo(BlockGroup o) {
            if (o.size == this.size) {
                if (o.rainBowCount == this.rainBowCount) {
                    if (o.x == this.x) return o.y - this.y;
                    return o.x - this.x;
                }
                return o.rainBowCount - this.rainBowCount;
            }
            return o.size - this.size;
        }
    }
}