백준 20058 마법사 상어와 파이어스톰

문제

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

코드

package com.company;
// 4방향중 3칸 이상이 얼음이 아니면 1씩 감소
// 얼음이 0이여도 계속 감소가 되는지 확인
// 배열 회전
import java.util.*;

public class Main {
    static int n,q;
    static int[][] board;
    static int[][] d={{0,1},{0,-1},{1,0},{-1,0}};
    static void rotate(int y,int x,int l){
        int[][] temp=new int[l][l];
        for(int i=0;i<l;i++){
            for(int j=0;j<l;j++){
                int ny=i+x;
                int nx=l-1-j+y;
                temp[i][j]=board[nx][ny];
            }
        }
        for(int i=0;i<l;i++){
            for(int j=0;j<l;j++){
                int ny=y+i;
                int nx=x+j;
                board[ny][nx]=temp[i][j];
            }
        }
    }
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        n = (int) Math.pow(2, sc.nextInt());
        q = sc.nextInt();
        sc.nextLine();
        board = new int[n][n];
        int sum=0;
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                board[i][j] = sc.nextInt();
            }
        }

        //q 만큼 반복
        for (int k = 0; k < q; k++) {
            int l = (int) Math.pow(2, sc.nextInt());
            // 배열을 나눠서 회전
            for(int i=0;i<n/l;i++){
                for(int j=0;j<n/l;j++){
                    int y=i*l;
                    int x=j*l;
                    rotate(y,x,l);
                }
            }

            LinkedList<Pair> list=new LinkedList<>();
            // 배열 전체를 돌면서 얼음 양이 감소되는 좌표 찾기
            for(int i=0;i<n;i++){
                for(int j=0;j<n;j++){
                    int cnt=0;
                    for(int a=0;a<4;a++){
                        int y=i+d[a][0];
                        int x=j+d[a][1];
                        if(y<0 || y>=n || x<0 || x>=n || board[y][x]==0) continue;
                        cnt+=1;
                    }
                    if(cnt<3){
                        list.add(new Pair(i,j));
                    }
                }
            }
            // 좌표를 돌면서 얼음양 감소
            for(Pair p:list){
                if (board[p.y][p.x]>0){
                    board[p.y][p.x]-=1;
                }
            }
        }
        // 전체 board를 순회돌면서 bfs를 사용해서 덩어리 카운팅
        int[][] visited=new int[n][n];
        Queue<Pair> q=new LinkedList<>();
        int answer=0;
        for(int i=0;i<n;i++){
            for(int j=0;j<n;j++){
                sum+=board[i][j];
                if(visited[i][j]==1) continue;
                q.add(new Pair(i,j));
                int cnt=0;
                while(!q.isEmpty()){
                    Pair p=q.poll();
                    int y=p.y;
                    int x=p.x;

                    for(int k=0;k<4;k++){
                        int ny=y+d[k][0];
                        int nx=x+d[k][1];

                        if(ny<0 || ny>=n || nx<0 || nx>=n || board[ny][nx]==0 || visited[ny][nx]==1) continue;
                        visited[ny][nx]=1;
                        q.add(new Pair(ny,nx));
                        cnt++;
                    }
                }
                answer=Math.max(answer,cnt);
            }
        }
        System.out.println(sum);
        System.out.println(answer);
    }
    static class Pair{
        public int y;
        public int x;

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

풀이

시뮬레이션과 bfs를 사용한 문제인데 문제 설명이 애매해서 헷갈렸습니다
확인해야할 사항들

• 4방향중 3칸이상이 얼음이 아니면 1씩 감소
• 얼음이 0이면 감소가 되면 안됨
• 전체 배열을 확인 후 한번에 얼음양을 감소시켜야 됨
• 배열이 회전되었는지 확인