[백준 10058 Java] 마법사 상어와 파이어스톰

회전하기 전 :

0 0	0 1	0 2	0 3	0 4	0 5
1 0	1 1	1 2	1 3	1 4	1 5
2 0	2 1	2 2	2 3	2 4	2 5
3 0	3 1	3 2	3 3	3 4	3 5
4 0	4 1	4 2	4 3	4 4	4 5
5 0	5 1	5 2	5 3	5 4	5 5

 

 

회전한 후 :

2 0	1 0	0 0	2 3	1 3	0 3
2 1	1 1	0 1	2 4	1 4	0 4
2 2	1 2	0 2	2 5	1 5	0 5
5 0	4 0	3 0	5 3	4 3	3 3
5 1	4 1	3 1	5 4	4 4	3 4
5 2	4 2	3 2	5 5	4 5	3 5

 

 

	첫번째 회색 네모	제일 아래 흰색 네모	제일 위 흰색 네모	마지막 회색 네모
특징	아래로 0번, 오른쪽으로 0번 감	아래로 1번 L칸, 오른쪽으로 0번 감	아래로 0번, 오른쪽으로 1번 L칸 감	아래로 1번 L칸, 오른쪽으로 1번 L칸 감
이동	0, 0 > 0, 2 0, 1 > 1, 2 0, 2 > 2, 2 1, 0 > 0, 1 1, 1 > 1, 1 1, 2 > 2, 1	3, 0 > 3, 2 3, 1 > 4, 2 3, 2 > 5, 2 4, 0 > 3, 1 4, 1 > 4, 1 4, 2 > 5, 1	0, 3 > 0, 5 0, 4 > 1, 5 0, 5 > 2, 5 1, 3 > 0, 4 1, 4 > 1, 4 1, 5 > 2, 4	3, 3 > 3, 5 3, 4 > 4, 5 3, 5 > 5, 5 4, 3 > 3, 4 4, 4 > 4, 4 4, 5 > 5, 4
규칙	Y = X -X + 2= Y	Y + 3 = X -X + 2 + 3 =  Y	Y - 3 = X -X + 2 + 3 = Y	Y = X -X + 2 + 3 +3 = Y

 

회전된 결과의 X값은 Y = X식에,

회전된 결과의 Y값은 -X + (L-1) =  Y

• 아래로 N번 L칸 갈때마다 X > X-N*L
• 오른쪽으로 M번 L칸 갈때마다 Y > Y-N*L

로 치환 후, 변경된 항은 좌변으로 이항하여 정리

 

 

import java.util.*;

class Data{
	int i;
	int j;
	Data(int i, int j) {
		this.i = i;
		this.j = j;
	}
}
public class Main
{
    static int[][] base_pan;
    static int[][] rotate_pan;
    
    static int[] move_1 = {-1,1,0,0};
    static int[] move_2 = {-0, 0,-1,1};

	// L*L칸 격자를 한개씩 받아 회전시키는 함수
    public static void rotate(int L, int now_i_level, int now_j_level, int now_x, int now_y) {

        for(int i=now_x; i<now_x+L; i++) {
            for(int j=now_y; j<now_y+L; j++) {
                rotate_pan[j - L*now_j_level +L*now_i_level][ L*(now_i_level+1)-1 -i +L*now_j_level]=base_pan[i][j];
            }
        }
    }

    public static void main (String[] args) throws java.lang.Exception
    {
    	
    	ArrayList dap_list = new ArrayList();
    
        Scanner sc = new Scanner(System.in);
        int N = Integer.parseInt(sc.next());
        N = (int) (Math.pow(2, N));
        int Q = Integer.parseInt(sc.next());	// 몇 번 마법을 쓸건지
		int L = 0;	// 각 마법의 단계(몇 칸짜리 공격)

        base_pan = new int[N][N];		// 문제에서 제공하는 행렬(입력값)
        rotate_pan = new int[N][N];		// 회전된 행렬, 회전하는 동안 기존 행렬이 변경되면 안되기에 선언.
        int[][] ice_temp_pan = new int[N][N];	// 얼음과 이웃한 칸이 2칸 이하인 경우를 체크하는 행렬, 해당 작업중 기존 행렬이 변경되면 안되기에 선언.
        boolean[][] visit_pan = new boolean[N][N];	//가장 큰 얼음덩어리 구할 때, 방문체크

		int now_i=0;
		int now_j=0;
		int now_i_level = 0;		// 아래로 L칸씩 몇 번 움직였는지
		int now_j_level = 0;		// 오른쪽으로로 L칸씩 몇 번 움직였는지
		
    	int temp_i;		// 이웃한 칸을 체크하기 위한 변수
    	int temp_j;		// 이웃한 칸을 체크하기 위한 변수
    	int ice_cnt=0;	// 얼음과 인접한 칸의 개수를 세기 위한 변수
		
        for(int i=0; i<N; i++) {
            for (int j=0; j<N; j++) {
                base_pan[i][j] = Integer.parseInt(sc.next());
            }
        }
        
        for(int k=0; k<Q; k++) {

            L = Integer.parseInt(sc.next());
            L = (int)Math.pow(2, L);

			now_i=0;
			now_j=0;
			now_i_level = 0;
			now_j_level = 0;
			
			while( (now_i<N) ) {
				while( (now_j<N) ) {
					rotate(L, now_i_level, now_j_level, now_i, now_j);
	                now_j = now_j+L;
	                now_j_level++;
					
				}
				now_j=0;
				now_j_level=0;
				now_i = now_i+L;
				now_i_level++;
			}

	        base_pan = rotate_pan;	// 회전된 행렬로 교체

			// 얼음과 이웃한 칸이 2칸 이하인지 체크하는 부분
	        for(int i=0; i<N; i++) {
	        	ice_temp_pan[i] = Arrays.copyOf(base_pan[i], base_pan[i].length);	// 현재 행렬을 copy
	            for (int j=0; j<N; j++) {
	            	ice_cnt=0;
	            	for (int m=0; m<4; m++) {
	            		temp_i = i+move_1[m];
	            		temp_j = j+move_2[m];
	            		if(temp_i<0 || temp_i>=N ||temp_j<0 || temp_j>=N) {
	            			continue;
	            		}
	            		if( base_pan[temp_i][temp_j]>0  ) {
	            			ice_cnt++;
	            		}
	            	}
	            	
	            	if(ice_cnt<3) {	// 얼음과 이웃한 칸이 2칸 이하면 얼음의 양을 1 감소 시킴. 음수일 경우는 0으로 치환.
	            		ice_temp_pan[i][j]=ice_temp_pan[i][j]-1;
	            		if(ice_temp_pan[i][j]<0) {
	            			ice_temp_pan[i][j]=0;
	            		}
	            	}
	                
	            }
	        }
	        
	        base_pan = ice_temp_pan;	// 변경된 얼음의 양으로 교체

        }
        
        int ice_acc = 0;	// 총 얼음의 양
		// 각 얼음 덩어리별로 칸을 세기위해 ice_cnt를 재사용^^
        Queue que = new LinkedList();
        int org_i;
        int org_j;

        for(int i=0; i<N; i++) {
            for (int j=0; j<N; j++) {
                if( visit_pan[i][j] ) {
                	continue;
                }
                if( base_pan[i][j]>0  ) {
                	ice_acc = ice_acc+base_pan[i][j];
        			visit_pan[i][j]=true;
        			ice_cnt=1;
                	que.offer(new Data(i,j));
                	while( !que.isEmpty() ) {
                		org_i = ((Data)que.peek()).i;
                		org_j = ((Data)que.peek()).j;
                		que.poll();
    	            	for (int m=0; m<4; m++) {
    	            		temp_i = org_i+move_1[m];
    	            		temp_j = org_j+move_2[m];
    	            		if(temp_i<0 || temp_i>=N ||temp_j<0 || temp_j>=N) {
    	            			continue;
    	            		}
    	                    if( visit_pan[temp_i][temp_j] ) {
    	                    	continue;
    	                    }
    	            		if( base_pan[temp_i][temp_j]>0  ) {
    	            			que.offer(new Data(temp_i,temp_j));
    	            			visit_pan[temp_i][temp_j]=true;
    	            			ice_acc = ice_acc+base_pan[temp_i][temp_j];
    	            			ice_cnt++;
    	            		}
    	            	}
    	            	
                	}
                	dap_list.add(ice_cnt);
                }
            }
        }


        int temp_ice_cnt;
        for (int i=0; i<dap_list.size(); i++) {
        	temp_ice_cnt = (int) dap_list.get(i);
        	if(ice_cnt<temp_ice_cnt) {
        		ice_cnt = temp_ice_cnt;
        	}
        }
        System.out.println(ice_acc);	// 모든 얼음의 양
        System.out.println(ice_cnt);	// 가장 큰 덩어리의 칸

    }

}