[BOJ/JAVA] 20058번: 마법사 상어와 파이어스톰

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

20058번: 마법사 상어와 파이어스톰

키워드

• 크기가 2^N × 2^N인 격자로 나누어진 얼음판
• 위치 (r, c)는 격자의 r행 c열을 의미
• A[r][c]는 (r, c)에 있는 얼음의 양을 의미한다.
• A[r][c]가 0인 경우 얼음이 없는 것이다.
• 파이어스톰
  • 먼저 격자를 2^L × 2^L 크기의 부분 격자로 나눈다.
  • 모든 부분 격자를 시계 방향으로 90도 회전시킨다.
  • 얼음이 있는 칸 3개 또는 그 이상과 인접해있지 않은 칸은 얼음의 양이 1 줄어든다.
• 파이어스톰을 총 Q번 시전
• 남아있는 얼음 A[r][c]의 합
• 남아있는 얼음 중 가장 큰 덩어리가 차지하는 칸의 개수

---

구현

중요한 점은 N, L을 이용하여 나타내는 값은 모두 2의 제곱수 라는 것이다.

가장 먼저 파이어스톰을 구현하자

• 격자를 2^L을 step으로 하여 반복한다.
• 이후 각 부분 행렬을 돌리는 알고리즘을 구현한다.
  • 행렬을 돌리는 알고리즘은 다음과 같다.
    • N*N크기의 행렬이라고 하면, [i][j] → [N-j-1][i] 가 된다.
    • 중요한 점은 시작하는 인덱스의 위치도 반영해야 하므로 최종적으로는 다음과 같다
    • [y + i][x + j] = [y + N - j - 1][x + i]
• DFS를 이용하여 [0][0] 부터 [2^N-1][2^N-1] 까지 녹을 수 있는 얼음이 있는지 확인하고, 녹일 얼음의 위치를 기억한다.
• 녹일 얼음을 동시에 녹인다.
• 위 파이어스톰을 Q번 반복한다.
• 남아있는 얼음 중 가장 큰 덩어리가 차지하는 칸의 개수 세기
  • DFS를 이용하여 한 지점으로부터 연결된 것이 가장 큰 것을 반환한다.

---

코드

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

// 1. 2차원 배열 돌리기
// 2. DFS

public class java_20058 {
    final static int dydx[][] = { { -1, 0 }, { 1, 0 }, { 0, -1 }, { 0, 1 } };

    final static int twoPow[] = { 1, 2, 4, 8, 16, 32, 64 };

    static int board[][];
    static int boardTmp[][];

    static int N;
    static int Q;

    static List<Pair> fireList;

    static boolean[][] isVisited;

    static int sumOfIce = 0;

    static class Pair {
        int y, x;

        public Pair(int y, int x) {
            this.y = y;
            this.x = x;
        }
    }

    // fireStorm
    public static void fireStorm(int q) {
        storm(q);

        for (int i = 0; i < board.length; i++) {
            board[i] = Arrays.copyOf(boardTmp[i], board.length);
        }

        fire();

        for (int i = 0; i < board.length; i++) {
            board[i] = Arrays.copyOf(boardTmp[i], board.length);
        }

    }

    // [y][x] 부터 length 만큼 돌리기
    public static void rotate(int y, int x, int length) {
        for (int i = 0; i < length; i++) {
            for (int j = 0; j < length; j++) {
                boardTmp[y + i][x + j] = board[y + length - j - 1][x + i];
            }
        }
    }

    // storm
    // 1. 돌리기
    public static void storm(int q) {
        // 2^q * 2^q
        for (int i = 0; i < board.length; i += twoPow[q]) {
            for (int j = 0; j < board.length; j += twoPow[q]) {
                rotate(i, j, twoPow[q]);
            }
        }
    }

    public static int DFS(int y, int x) {
        int count = 0;
        sumOfIce += board[y][x];

        for (int i = 0; i < dydx.length; i++) {

            int toY = y + dydx[i][0];
            int toX = x + dydx[i][1];

            try {
                if (!isVisited[toY][toX]) {
                    if (board[toY][toX] > 0) {
                        count++;
                        isVisited[toY][toX] = true;
                        count += DFS(toY, toX);
                    }
                }
            } catch (IndexOutOfBoundsException e) {
                continue;
            }
        }
        return count;
    }

    // fire
    // 2. 녹이기
    public static void fire() {
        for (int i = 0; i < board.length; i++) {
            boardTmp[i] = Arrays.copyOf(board[i], board.length);
        }

        for (int i = 0; i < board.length; i++) {
            for (int j = 0; j < board.length; j++) {
                int count = 0;
                for (int k = 0; k < dydx.length; k++) {
                    int toY = i + dydx[k][0];
                    int toX = j + dydx[k][1];

                    try {
                        if (board[toY][toX] > 0) {
                            count++;
                        }
                    } catch (ArrayIndexOutOfBoundsException e) {
                        continue;
                    }
                }
                if (count < 3) {
                    if (board[i][j] > 0) {
                        boardTmp[i][j] -= 1;
                    }
                }
            }
        }
    }

    // countIce
    public static int countIce() {
        int result = 0;

        isVisited = new boolean[board.length][board.length];

        for (int i = 0; i < board.length; i++) {
            for (int j = 0; j < board.length; j++) {
                // 방문하지 않았어야 함
                if (!isVisited[i][j]) {
                    // 얼음이여야 함
                    if (board[i][j] > 0) {
                        isVisited[i][j] = true;
                        int count = DFS(i, j) + 1;
                        result = Math.max(result, count);
                    }
                }
            }
        }

        return result;
    }

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

        StringTokenizer st = new StringTokenizer(br.readLine());

        N = Integer.parseInt(st.nextToken());

        Q = Integer.parseInt(st.nextToken());

        board = new int[twoPow[N]][twoPow[N]];
        boardTmp = new int[twoPow[N]][twoPow[N]];

        // 데이터 삽입
        for (int i = 0; i < board.length; i++) {
            st = new StringTokenizer(br.readLine());
            for (int j = 0; j < board[0].length; j++) {
                board[i][j] = Integer.parseInt(st.nextToken());
            }
        }

        for (int i = 0; i < board.length; i++) {
            boardTmp[i] = Arrays.copyOf(board[i], board.length);
        }

        st = new StringTokenizer(br.readLine());
        for (int i = 0; i < Q; i++) {
            // 파이어스톰
            fireStorm(Integer.parseInt(st.nextToken()));
        }

        for (int i = 0; i < board.length; i++) {
            for (int j = 0; j < board.length; j++) {
                if (board[i][j] > 0) {
                    sumOfIce += board[i][j];
                }
            }
        }

        System.out.println(sumOfIce);
        // 가장 큰 얼음덩어리가 차지하는 칸의 갯수
        System.out.println(countIce());

        br.close();
    }
}

---