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

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

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;

public class Main_BOJ_20058 {
	static int[] dr= {-1,1,0,0};
	static int[] dc= {0,0,-1,1};
	static int N, Q, len;
	static int[][] A;
	static boolean[][] visited;
	static int totalIce=0;
	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());
		len=(int)Math.pow(2, N);
		A=new int[len][len];
		visited=new boolean[len][len];
		for (int i=0; i<len; i++) {
			st=new StringTokenizer(br.readLine());
			for (int j=0; j<len; j++) {
				A[i][j]=Integer.parseInt(st.nextToken());
			}
		}
		st=new StringTokenizer(br.readLine());
		for (int i=0; i<Q; i++) {
			int L=Integer.parseInt(st.nextToken());
			divide((int)Math.pow(2, L));
			removeIce();
		}
		int biggestIce=checkIce();
		System.out.println(totalIce);
		System.out.println(biggestIce);
	}
	private static void divide(int size) {
		for (int r=0; r<len; r+=size) {
			for (int c=0; c<len; c+=size) {
				rotate(r,c,size);
			}
		}
	}
	
	private static void rotate(int r, int c, int size) {
		int[][] temp=new int[size][size];
		for (int i=0; i<size; i++) {
			for (int j=0; j<size; j++) {
				temp[i][j]=A[r+(size-j-1)][c+i];
			}
		}
		for (int i=r; i<r+size; i++) {
			for (int j=c; j<c+size; j++) {
				A[i][j]=temp[i-r][j-c];
			}
		}	
	}
	private static void removeIce() {
		boolean[][] check=new boolean[len][len];
		int nr, nc;
		for (int r=0; r<len; r++) {
			for (int c=0; c<len; c++) {
				if (A[r][c]==0) continue;
				int cnt=0;
				for (int d=0; d<4; d++) {
					nr=r+dr[d];
					nc=c+dc[d];
					if (nr<0 || nc<0 || nr>=len || nc>=len) continue;
					if (A[nr][nc]>0) cnt++;
				}
				if (cnt<3) check[r][c]=true;
			}
		}
		for (int r=0; r<len; r++) {
			for (int c=0; c<len; c++) {
				if (check[r][c]) A[r][c]-=1;
			}
		}
	}
	
	private static int checkIce() {
		int ans=0;
		for (int r=0; r<len; r++) {
			for (int c=0; c<len; c++) {
				if (A[r][c]>0 && !visited[r][c]) ans=Math.max(ans, bfs(r,c));
			}
		}
		return ans;
	}

	
	private static int bfs(int start_r, int start_c) {
		int bigIce=0;
		Queue<int[]> q=new LinkedList<>();
		q.add(new int[] {start_r,start_c});
		visited[start_r][start_c]=true;
		totalIce+=A[start_r][start_c];
		bigIce++;
		while (!q.isEmpty()) {
			int[] curr=q.poll();
			int r=curr[0];
			int c=curr[1];
			for (int i=0; i<4; i++) {
				int nr=r+dr[i];
				int nc=c+dc[i];
				if (nr<0 || nc<0 || nr>=len || nc>=len || A[nr][nc]==0 || visited[nr][nc]) continue;
				visited[nr][nc]=true;
				totalIce+=A[nr][nc];
				bigIce++;
				q.add(new int[] {nr,nc});
			}
			
		}
		return bigIce;
	}

}

문제의 조건에 따라 그대로 구현해주면 OK다.

시뮬레이션+구현+BFS/DFS 문제.