이번에 풀어본 문제는
백준 20058번 마법사 상어와 파이어스톰 입니다.

📕 문제 링크

❗️코드

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

class Point2
{
    int x,y;

    public Point2(int x, int y)
    {
        this.x = x;
        this.y = y;
    }
}
public class Main {
    static int N,Q;
    static int area;
    static int total;
    static boolean [][] visited;
    static int [][] map;
    static int [][] tmp_map;
    static int [] dx = {-1,1,0,0};
    static int [] dy = {0,0,-1,1};
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());

        N = (int)Math.pow(2,Integer.parseInt(st.nextToken()));
        Q = Integer.parseInt(st.nextToken());

        map = new int[N][N];

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

        st = new StringTokenizer(br.readLine());
        for(int i = 0; i < Q; ++i)
        {
            cast(Integer.parseInt(st.nextToken()));
            melt();
        }
        check();
        System.out.printf("%d\n%d",total,area);
    }
    static void cast(int n)
    {
        if(n < 1) return;
        tmp_map = new int[N][N];
        for(int i = 0; i < N; ++i) System.arraycopy(map[i],0,tmp_map[i],0,N);

        int l = (int)Math.pow(2,n);
        for(int i = 0; i < N; i+=l)
        {
            for(int j = 0; j < N; j+=l)
            {
                rotate(i,j,l);
            }
        }
    }
    static void rotate(int x, int y, int size)
    {
        for(int i = 0; i < size; ++i)
        {
            for(int j = 0; j < size; ++j)
            {
                map[x+j][y+size-i-1] = tmp_map[x+i][y+j];
            }
        }
    }
    static void melt()
    {
        Queue<Point2> tmp_q = new LinkedList<>();
        for(int i = 0; i < N; ++i)
        {
            for(int j = 0; j < N; ++j)
            {
                if(map[i][j] < 1) continue;
                int cnt = 0;
                for(int idx = 0; idx < 4; ++idx)
                {
                    int mx = i + dx[idx];
                    int my = j + dy[idx];

                    if(isValid(mx,my))
                    {
                        if(map[mx][my] > 0) cnt++;
                    }
                }
                if(cnt < 3) tmp_q.add(new Point2(i,j));
            }
        }

        while(!tmp_q.isEmpty())
        {
            Point2 tmp = tmp_q.poll();
            map[tmp.x][tmp.y]--;
        }
    }
    static void check()
    {
        visited = new boolean[N][N];
        Queue<Point2> q = new LinkedList<>();
        for(int i = 0; i < N; ++i)
        {
            for(int j = 0; j < N; ++j)
            {
                if(map[i][j] < 1) continue;
                total += map[i][j];
                if(!visited[i][j])
                {
                    q.add(new Point2(i,j));
                    visited[i][j] = true;
                    int cnt = 0;
                    while(!q.isEmpty())
                    {
                        Point2 cur = q.poll();
                        cnt++;

                        for(int idx = 0; idx < 4; ++idx)
                        {
                            int mx = cur.x + dx[idx];
                            int my = cur.y + dy[idx];

                            if(!isValid(mx,my) || visited[mx][my] || map[mx][my] < 1) continue;
                            visited[mx][my] = true;
                            q.add(new Point2(mx,my));
                        }
                    }
                    if(cnt == 1) continue;
                    if(cnt > area) area = cnt;
                }
            }
        }
    }
    static boolean isValid(int x, int y)
    {
        return x >= 0 && y >= 0 && x < N && y < N;
    }
}

📝 풀이

N^2 크기의 격자에서 스킬을 사용하면 2^L제곱 크기로 구간을 나누어 배열을 90도 회전시켜주고, 각 인덱스를 기준으로 상하좌우로 인접한 칸 중 남은 얼음의 양이 1이상인 칸의 개수가 3보다 작을경우 해당 칸 얼음의 양을 1 감소시켜주는 과정의 문제입니다.
L의 값이 Q개 입력되며, 해당 반복에서 cast함수에 L값을 넘겨주면 2^L 크기만큼 인덱스를 증가시키면서 rotate함수에 기준점이 될 좌표값과 사각형의 크기를 넘겨주게 됩니다. rotate함수에서는 해당 기준점으로부터 넘겨받은 크기 만큼의 사각형을 90도 회전시키는 과정을 수행합니다.
모든 회전이 끝나면, 얼음이 녹는 과정을 거칩니다.
값이 이미 0이하인 인덱스는 넘어가주고, 나머지 칸에서는 상하좌우 값을 판별하여 카운트값을 증가시켜, 3보다 작다면 해당 칸의 얼음의 양을 1 줄여줍니다.
한 반복에서 map의 값을 즉시 변경하게 되면, 다음 인덱스에서 조건을 판별할 때 영향을 주기 때문에, 좌표값만 큐에 담아두고 실제 값의 변경은 모든 탐색이 끝난 후에 하도록 했습니다.
위의 과정을 Q번 수행하고 나면 마지막 출력 조건인 전체 얼음의 양의 합, 가장 범위가 큰 덩어리의 크기를 출력해주면 해결됩니다.
덩어리를 구하려면 어차피 배열을 순회해야 하므로 동시에 진행했으며, 덩어리 크기는 bfs를 활용했습니다.

📜 후기

2차원 배열의 회전만 구현하면 쉬웠던 문제입니다.
배열을 여러 구간으로 나누어 회전을 시켜야 하기 때문에 생각보다 많이 헷갈렸고, 그부분에서 조금 시간을 빼앗겼던 것 같습니다.
항상 회전 문제에 많이 취약한 것 같은데, 헷갈리지만 얼른 적응 해야할 것 같습니다..