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

www.acmicpc.net/problem/20058

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

import java.io.*;
import java.util.*;

public class Main {
	static int[][] map, rotate;
	static int[] dy = { 1,-1,0,0 };
	static int[] dx = { 0, 0, 1, -1 };
	static boolean[][] visited;
	static int max;

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

		StringTokenizer st = new StringTokenizer(br.readLine());
		int N = Integer.parseInt(st.nextToken());
		int Q = Integer.parseInt(st.nextToken());

		int size = (int) Math.pow(2, N);
		map = new int[size][size];

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

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

		for (int k = 0; k < Q; k++) {
			int L = Integer.parseInt(st.nextToken());

			// 회전하기
			rotate = new int[size][size];
			divide(0, 0, N, size, L);

			// 복사
			for (int i = 0; i < size; i++) {
				for (int j = 0; j < size; j++) {
					map[i][j] = rotate[i][j];
				}
			}
			// 얼음 줄이기
			decreaseIce(size);
		}
		
		//닶 구하기
		int sum =0;
		visited = new boolean[size][size];
		for(int i=0; i<size; i++) {
			for(int j=0; j<size; j++) {
				sum += map[i][j];
				if(visited[i][j] || map[i][j] == 0) continue;
				bfs(i,j);
			}
		}
		
		System.out.println(sum);
		System.out.println(max);
	}

	private static void bfs(int i, int j) {
		Queue<Pos> qu = new LinkedList<>();
		qu.offer(new Pos(i,j));
		visited[i][j] = true;
		int iceCnt=1;
		
		while(!qu.isEmpty()) {
			int size = qu.size();
			
			for(int q=0; q<size; q++) {
				Pos pos = qu.poll();
				
				for(int k=0; k<4; k++) {
					int x = pos.x + dx[k];
					int y = pos.y + dy[k];
					
					if( x < 0 || x>=map.length || y<0 || y>=map.length || visited[x][y]) continue;
					if(map[x][y] == 0) continue;
					
					visited[x][y] = true;
					qu.offer(new Pos(x,y));
					iceCnt++;
				}
			}
		}
		
		max = Math.max(max, iceCnt);
	}

	private static void decreaseIce(int size) {
		int[][] decMap = new int[size][size];
		for(int i=0; i<size; i++) {
			for(int j=0; j<size; j++) {
				if(map[i][j] == 0) continue;
				if(!checkIce(i,j, size)) decMap[i][j]--;
			}
		}
		
		for(int i=0; i<size; i++) {
			for(int j=0; j<size; j++) {
				map[i][j] += decMap[i][j];
			}
		}
	}

	private static boolean checkIce(int i, int j, int size) {
		int count =0;
		for(int k=0; k<4; k++) {
			int x = i + dx[k];
			int y = j + dy[k];
			
			if( x < 0 || x>=size || y<0 || y>=size) continue;
			if(map[x][y] == 0) continue;
			
			count++;
		}
		
		if(count >=3) return true;
		return false;
	}

	public static void divide(int x, int y, int cnt, int size, int limit) {
		if (cnt == limit) {
			int mapSize = (int) Math.pow(2, limit);
			// 회전
			for(int i=x; i<x+mapSize; i++) {
				for(int j=y; j<y+mapSize; j++) {
					rotate[j-y+x][(y+mapSize)-1-i+x] = map[i][j];
				}
			}

			return;
		}

		int newSize = size / 2;

		divide(x, y, cnt - 1, newSize, limit);

		divide(x, y + newSize, cnt - 1, newSize, limit);

		divide(x + newSize, y, cnt - 1, newSize, limit);

		divide(x + newSize, y + newSize, cnt - 1, newSize, limit);
	}
	
	static class Pos{
		int x;
		int y;
		public Pos(int x, int y) {
			super();
			this.x = x;
			this.y = y;
		}
	}
}

정리

• 2L × 2L 크기의 부분 격자로 나눈다.
• 각 구격에서 시계 방향으로 90도 돌린다.
• 회전을 완료한 배열에 대해 "얼음이 있는 칸 3개 또는 그 이상과 인접해있지 않은 칸" 을 검사하여 얼음의 양을 1 줄여준다.
• 즉 2중 포문으로 각 자리마다 4방향으로 검사를 진행해 얼음 2개이하라면 해당 자리의 얼음을 -1 해준다.
• 연속적으로 일어나지 않기떄문에 따로 줄어든 얼음을 저장하는 배열에 정보를 담아놨다가 마지막에 적용해준다.
• 마지막으로 얼음의 합을 구하면서 BFS를 통해 구역을 나누어 가장 큰 얼음 덩어리를 구해준다. 

회전

90도 회전 같은 경우는 위의 그림과 같이

• 1행 값을 3열에
• 2행 값을 2열에
• 3행 값을 1열에 넣으면 된다.