마법사상어와파이어스톰 - 20058번(Java)

문제

마법사 상어는 파이어볼과 토네이도를 조합해 파이어스톰을 시전할 수 있다. 오늘은 파이어스톰을 크기가 2N × 2N인 격자로 나누어진 얼음판에서 연습하려고 한다. 위치 (r, c)는 격자의 r행 c열을 의미하고, A[r][c]는 (r, c)에 있는 얼음의 양을 의미한다. A[r][c]가 0인 경우 얼음이 없는 것이다.

파이어스톰을 시전하려면 시전할 때마다 단계 L을 결정해야 한다. 파이어스톰은 먼저 격자를 2L × 2L 크기의 부분 격자로 나눈다. 그 후, 모든 부분 격자를 시계 방향으로 90도 회전시킨다. 이후 얼음이 있는 칸 3개 또는 그 이상과 인접해있지 않은 칸은 얼음의 양이 1 줄어든다. (r, c)와 인접한 칸은 (r-1, c), (r+1, c), (r, c-1), (r, c+1)이다. 아래 그림의 칸에 적힌 정수는 칸을 구분하기 위해 적은 정수이다.

마법사 상어는 파이어스톰을 총 Q번 시전하려고 한다. 모든 파이어스톰을 시전한 후, 다음 2가지를 구해보자.

1. 남아있는 얼음 A[r][c]의 합
2. 남아있는 얼음 중 가장 큰 덩어리가 차지하는 칸의 개수

얼음이 있는 칸이 얼음이 있는 칸과 인접해 있으면, 두 칸을 연결되어 있다고 한다. 덩어리는 연결된 칸의 집합이다.

입력

첫째 줄에 N과 Q가 주어진다. 둘째 줄부터 2N개의 줄에는 격자의 각 칸에 있는 얼음의 양이 주어진다. r번째 줄에서 c번째 주어지는 정수는 A[r][c] 이다.

마지막 줄에는 마법사 상어가 시전한 단계 L1, L2, ..., LQ가 순서대로 주어진다.

출력

첫째 줄에 남아있는 얼음 A[r][c]의 합을 출력하고, 둘째 줄에 가장 큰 덩어리가 차지하는 칸의 개수를 출력한다. 단, 덩어리가 없으면 0을 출력한다.

제한

• 2 ≤ N ≤ 6
• 1 ≤ Q ≤ 1,000
• 0 ≤ A[r][c] ≤ 100
• 0 ≤ Li ≤ N

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

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

package Samsung;

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

import java.util.*;

public class 마법사상어와파이어스톰 {
	
	
	static int n,q;
	static StringTokenizer st;
	static int[][] arr;
	static int sz;
	static int dx[] = {-1,1,0,0};
	static int dy[] = {0,0,-1,1};
	
	
	public static void print() {
		
		for(int i=0; i<sz;i++) {
			for(int j=0; j<sz; j++) {
				
				System.out.print(arr[i][j]+" ");
			}
			
			System.out.println();
		}
		
		System.out.println();
	}
	
	
	public static boolean cango(int x, int y) {
		
		return x>=0 && x<sz &&y>=0 && y<sz;
	}
	
	static class Pair{
		
		int x; int y;
		
		Pair(int x, int y){
			this.x =x;
			this.y = y;
		}
	}
	
	public static int search(int i, int j ,boolean[][]check) { //가장 큰덩어리를 찾는 코드 -> bfs를 써서 가장 큰 덩어리를 찾는다
		
		
		Queue<Pair>q =new LinkedList<>();
		q.add(new Pair(i,j));
		check[i][j]=true;
		
		int cnt =1;
		
		while(!q.isEmpty()) {
			
			Pair p = q.poll();
			int x = p.x;
			int y = p.y;
			
			for(int t=0; t<4; t++) {
				
				int nx = x+dx[t];
				int ny = y+dy[t];
				if(cango(nx,ny)&&check[nx][ny]==false&&arr[nx][ny]>0) {
					
					q.add(new Pair(nx,ny));
					check[nx][ny]=true;
					cnt++;
				}
			}
		}
		
		return cnt;
		
		
	}
	
	
	public static void rotate(int sx , int sy, int ex, int ey, int msz,int[][]tmp) {
		
		int[][]narr = new int[msz][msz];
		
		for(int i=sx; i<=ex; i++) {  // 어려웠던점1.오른 쪽으로 90도 rotate하는 것이 어려웠다.
			
			int[]list=arr[i]; //arr 의 i 행을 받아온다
			for(int t= sy; t<=ey; t++) { //list의 sy~ey 를 narr에 행을 바꿔가며(t-sy)넣어준다
				narr[t-sy][sx+msz-i-1]=list[t];
			}
			
		}
		
		
		
		for(int i=sx; i<=ex; i++) {
			for(int j=sy; j<=ey; j++) {
				
				tmp[i][j]=narr[i-sx][j-sy];
				
			}
		}
		
	
		
		
		
	}
	
	
	
	public static void doMagic(int l) {
		
		int msz = (int)Math.pow(2, l);
		
		int [][]tmp = new int[sz][sz];
		
		for(int i=0; i<sz; i=i+msz) { 
			for(int j=0;j<sz; j=j+msz) {
				
				rotate(i,j,i+msz-1,j+msz-1,msz,tmp); //rotate 할 수 있는 지점을 모두 rotate 시켜준다
				
			}
		}

		for(int i=0; i<sz; i++) {
			for(int j=0; j<sz; j++) {
				arr[i][j]=tmp[i][j]; 
			}
		}
		
		for(int i=0; i<sz; i++) {
			for(int j=0; j<sz; j++) {
				
				int x = i;
				int y = j;
				
				int cnt =0;
				
			if(arr[x][y]>0) { //얼음이 있는 자리 일경우
				for(int t=0; t<4; t++) {  //4방향 탐색을 해서 0이 아닌 값이 있으면 cnt 를 늘려준다.
					
					int nx =x+dx[t];
					int ny =y+dy[t];
					
					if(!cango(nx,ny)) { continue;}
					if(arr[nx][ny]!=0) {cnt++;}
					
				}
				
				if(cnt<3 && tmp[x][y]>0) { //cnt 값이 3보다 작을경우 1을 감소시킨다.
					--tmp[x][y];
				}
			}
				
			}
		}
		
		for(int i=0; i<sz; i++) {
			for(int j=0; j<sz; j++) {
				arr[i][j]=tmp[i][j];
			}
		}
		
	//	print();
		
	}
	
	
	public static void main(String[] args) throws NumberFormatException, IOException {
		
		
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		st = new StringTokenizer(br.readLine());
		
		n = Integer.parseInt(st.nextToken());
		q = Integer.parseInt(st.nextToken());
		
		sz =(int)Math.pow(2,n); //배열 전체 크기 구하기 
		
		arr = new int[sz][sz];
		
		for(int i=0; i<sz; i++) {
			st = new StringTokenizer(br.readLine());
			for(int j=0; j<sz; j++) {
				
				arr[i][j]= Integer.parseInt(st.nextToken());
			}
		}
		
		st = new StringTokenizer(br.readLine());
		
		for(int i=0; i<q; i++) {
			
			int magic = Integer.parseInt(st.nextToken()); //사각형을 몇개 단위로 쪼갤 것인지
			doMagic(magic); //magic 크기만큼 rotate를 시켜준다
			
		}
		
		int ans1 =0;
		for(int i=0; i<sz; i++) {
			for(int j=0; j<sz; j++) {
				
				ans1+=arr[i][j]; //전체 얼음 개수를 구해준다
				
			}
		}
		
		int ans2 =0;
		
		boolean[][] check = new boolean[sz][sz];
		for(int i=0; i<sz; i++) {
			for(int j=0; j<sz; j++) {
				
				if(check[i][j]!=true && arr[i][j]>0) {
				int res = search(i,j,check); //bfs로 가장 큰 얼음덩어리 크기를 구해준다.
				ans2 = Math.max(ans2,res);
				}
				
			}
		}
		
		System.out.println(ans1);
		System.out.println(ans2);
		
	}

}

어려웠던점: 특정위치에서 일정 크기만큼 오른 쪽 90도 rotate 시키는 것