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

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

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

---

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

public class Main {
	
	static int N, n, Q, count;
	static int[][] map;
	static int[][] temp_map;
	static int[][] dir = {{0,1}, {0,-1}, {1,0}, {-1,0}};
	static boolean[][] visited;
	
	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());
		
		n = (int)Math.pow(2, N);
		
		map = new int[n][n];
		temp_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++) {
			int temp = (int)Math.pow(2, Integer.parseInt(st.nextToken()));
			
			// map -> temp_map 복사
			for(int j=0; j<n; j++) {
				for(int k=0; k<n; k++) {
					temp_map[j][k] = map[j][k];
				}
			}
			
			// 왼쪽위 꼭짓점에서 temp 만큼 회전
			for(int j=0; j<n; j+=temp) {
				for(int k=0; k<n; k+=temp) {
					rotate(j, k, temp);
				}
			}
			
			// 얼음이 있는 칸 3개 or 그 이상과 인접해 있지 않은 칸은 얼음의 양이 1 줄어든다.
			down();
		}		
		
		
		int sum = 0;
		
		// 남아있는 얼음의 합
		for(int i=0; i<n; i++) {
			for(int j=0; j<n; j++) {
				sum += map[i][j];
			}
		}
		
		int answer = 0;
		
		visited = new boolean[n][n];
		
		// 가장 큰 덩어리가 차지하는 칸의 개수
		for(int i=0; i<n; i++) {
			for(int j=0; j<n; j++) {
				if(!visited[i][j] && map[i][j] != 0) {
					count = 1;
					getBigIce(i, j);
					answer = Math.max(answer, count);
				}
			}
		}
		
		System.out.println(sum);
		System.out.println(answer);
		
	}
	
	public static void getBigIce(int x, int y) {
		visited[x][y] = true;
		
		for(int i=0; i<4; i++) {
			int nx = x + dir[i][0];
			int ny = y + dir[i][1];
			
			if(isInside(nx, ny) && !visited[nx][ny] && map[nx][ny] != 0) {
				count++;
				getBigIce(nx, ny);
			}
		}
	}
	
	public static void down() {
		visited = new boolean[n][n];
		
		for(int i=0; i<n; i++) {
			for(int j=0; j<n; j++) {
				int cnt = 0;
				
				for(int k=0; k<4; k++) {	
					int nx = i + dir[k][0];
					int ny = j + dir[k][1];
					
					if(isInside(nx, ny) && map[nx][ny] != 0) cnt++;
				}
				
				if(cnt < 3) visited[i][j] = true; 
				
			}
		}
		
		for(int i=0; i<n; i++) {
			for(int j=0; j<n; j++) {
				if(visited[i][j] && map[i][j] > 0) map[i][j]--;
			}
		}
	}
	
	public static boolean isInside(int x, int y) {
		return x>=0 && y>=0 && x<n && y<n;
	}
	
	public static void rotate(int x, int y, int len) {
		
		int temp_y=0;
		for(int i=x; i<x+len; i++) {
			int temp_x = 0;
			for(int j=y; j<y+len; j++) {
				map[x+temp_x][y+len-1-temp_y] = temp_map[i][j];
				temp_x++;
			}
			temp_y++;
		}
		
	}
	
	public static void print() {
		for(int i=0; i<n; i++) {
			for(int j=0; j<n; j++) {
				System.out.print(map[i][j] + " ");
			}
			System.out.println();
		}
		System.out.println();
	}
}