[BaekJoon] 20058 마법사 상어와 파이어스톰 (Java)

1.  문제 링크

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

2.  문제

요약

• 파이어스톰을 크기가 $2^N$ x $2^N$인 격자로 나누어진 연습판에서 연습하려고 하는데, 위치 (r, c)는 격자의 r행 c열을 의미하고, A[r][c]는 (r, c)에 있는 얼음의 양을 의미합니다.
• A[r][c]가 0인 경우 얼음이 없는 것입니다.
• 파이어스톰을 시전하려면 시전할 때마다 단계 L을 결정해야 합니다.
• 파이어스톰은 먼저 격자를 $2^L$ x $2^L$ 크기의 부분 격자로 나눕니다.
• 그 후, 모든 부분 격자를 시계 방향으로 90도 회전시킵니다.
• 이후 얼음이 있는 칸 3개 또는 그 이상과 인접해있지 않은 칸은 얼음의 양이 1 줄어듭니다.
  • (r, c)와 인접한 칸은 (r - 1, c), (r + 1, c), (r, c - 1), (r, c + 1)입니다.
• 마법사 상어는 파이어스톰을 총 Q번 시전하려고 합니다.
• 모든 파이어스톰을 시전한 후, 다음 2가지를 구하는 문제입니다.
  1. 남아있는 얼음 A[r][c]의 합
  2. 남아있는 얼음 중 가장 큰 덩어리가 차지하는 칸의 개수
• 얼음이 있는 칸이 얼음이 있는 칸과 인접해 있으면, 두 칸을 연결되어 있다고 합니다. 덩어리는 연결된 칸의 집합입니다.
• 입력: 첫 번째 줄에 2보다 크거나 같고 6보다 작거나 같은 N과 1보다 크거나 같고 1,000보다 작거나 같은 Q가 주어지고 두 번째 줄부터 $2^N$개의 줄에 격자의 각 칸에 있는 얼음의 양이 주어집니다. r번째 줄에서 c번째 주어지는 정수는 A[r][c]입니다. 마지막 줄에는 마법사 상어가 시전한 단계 $L_1, L_2, ..., L_Q$가 순서대로 주어집니다.
• 출력: 첫 번째 줄에 남아있는 얼음 A[r][c]의 합을 출력하고, 두 번째 줄에 가장 큰 덩어리가 차지하는 칸의 개수를 출력합니다. 단, 덩어리가 없으면 0을 출력합니다.

3.  소스코드

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

public class Main {
    static StringBuilder sb = new StringBuilder();
    static int N, Q, size, eachMassSize;
    static int[][] A;
    static int[] levels, dx = {-1, 0, 1, 0}, dy = {0, -1, 0, 1};;
    static void input() {
        Reader scanner = new Reader();
        N = scanner.nextInt();
        Q = scanner.nextInt();
        size = (int)Math.pow(2, N);
        A = new int[size][size];
        levels = new int[Q];
        for(int row = 0; row < size; row++) {
            for(int col = 0; col < size; col++) A[row][col] = scanner.nextInt();
        }
        for(int idx = 0; idx < Q; idx++) levels[idx] = scanner.nextInt();
    }

    static void solution() {
        for(int idx = 0; idx < Q; idx++) fireStorm(levels[idx]);
        int[] answer = findAnswers();
        for(int idx = 0; idx < answer.length; idx++)
            sb.append(answer[idx]).append('\n');
        System.out.print(sb);
    }

    static int[] findAnswers() {
        boolean[][] visited = new boolean[size][size];
        int total = 0;
        int maxSize = 0;
        for(int row = 0; row < size; row++) {
            for(int col = 0; col < size; col++) {
                total = sum(row, col, total);
                if(!visited[row][col] && A[row][col] != 0) {
                    eachMassSize = 0;
                    dfs(row, col, visited);
                    maxSize = Math.max(maxSize, eachMassSize);
                }
            }
        }
        int[] answer = {total, maxSize};
        return answer;
    }

    static void dfs(int x, int y, boolean[][] visited) {
        if(visited[x][y]) return;
        visited[x][y] = true;
        eachMassSize++;
        for(int dir = 0; dir < 4; dir++) {
            int cx = x + dx[dir], cy = y + dy[dir];
            if(isInMap(cx, cy)) {
                if(!visited[cx][cy] && A[cx][cy] != 0)
                    dfs(cx, cy, visited);
            }
        }
    }

    static int sum(int row, int col, int total) {
        return total + A[row][col];
    }

    static void fireStorm(int level) {
        rotate(level);
        melt();
    }

    static void melt() {
        boolean[][] isMelt = findMeltPoint();
        meltPoints(isMelt);
    }

    static void meltPoints(boolean[][] isMelt) {
        for(int row = 0; row < size; row++) {
            for(int col = 0; col < size; col++) {
                if(isMelt[row][col]) A[row][col]--;
            }
        }
    }

    static boolean[][] findMeltPoint() {
        boolean[][] isMelt = new boolean[size][size];
        for(int row = 0; row < size; row++) {
            for(int col = 0; col < size; col++) {
                if(A[row][col] == 0) continue;
                int count = 0;
                for(int dir = 0; dir < 4; dir++) {
                    int cx = row + dx[dir], cy = col + dy[dir];
                    if(isInMap(cx, cy)) {
                        if(A[cx][cy] != 0) count++;
                    }
                }
                if(count < 3) isMelt[row][col] = true;
            }
        }
        return isMelt;
    }

    static boolean isInMap(int x, int y) {
        if(x >= 0 && x < size && y >= 0 && y < size) return true;
        return false;
    }

    static void rotate(int level) {
        int numbers = (int)Math.pow(2, N * 2 - level * 2);
        int levelSize = (int)Math.pow(2, level);
        int row = 0, col = 0;
        for(int count = 0; count < numbers; count++) {
            rotateEachPart(row, col, row + levelSize - 1, col + levelSize - 1);
            row += levelSize;
            if(row == size) {
                row = 0;
                col += levelSize;
            }
        }
    }

    static void rotateEachPart(int startX, int startY, int endX, int endY) {
        int[][] rotateArr = new int[endX - startX + 1][endY - startY + 1];
        for(int col = startY; col <= endY; col++) {
            for(int row = endX; row >= startX; row--)
                rotateArr[col - startY][endX - row] = A[row][col];
        }

        for(int row = startX; row <= endX; row++) {
            for(int col = startY; col <= endY; col++)
                A[row][col] = rotateArr[row - startX][col - startY];
        }
    }

    public static void main(String[] args) {
        input();
        solution();
    }

    static class Reader {
        BufferedReader br;
        StringTokenizer st;
        public Reader() {
            br = new BufferedReader(new InputStreamReader(System.in));
        }
        String next() {
            while(st == null || !st.hasMoreElements()) {
                try {
                    st = new StringTokenizer(br.readLine());
                } catch (IOException e) {
                    e.printStackTrace();
                }
            }
            return st.nextToken();
        }
        int nextInt() {
            return Integer.parseInt(next());
        }
    }
}