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

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

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

package 시뮬레이션;

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 boj_20058_마법사상어와파이어스톰 {
	static int sum,group,N,Q,map[][],copyMap[][], Llist[];
	static  boolean visited[][];
	static int dx[]= {0,0,-1,1};
	static int dy[]= {-1,1,0,0};
	
	public static void main(String[] args) throws IOException {
		
		BufferedReader br= new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());
		
		sum=0;
		group=0;
		N=Integer.parseInt(st.nextToken());
		Q=Integer.parseInt(st.nextToken());
		
		int size=(int) Math.pow(2, N);
		map = new int[size][size];
		visited = new boolean[size][size];
		Llist= new int[Q];
		
		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 i=0; i<Q; i++) {
			Llist[i]=Integer.parseInt(st.nextToken());
		}
		
		solve(size);
		System.out.println(sum);
		System.out.println(group);
	}
	private static void solve(int size) {
		for(int i=0; i<Q; i++) { //Q번만큼 반복
			
			int L=(int) Math.pow(2, Llist[i]);
			copyMap=new int[size][size];
			
			int x=0, y=0;
			while(true) {	//1 격자를 2^L 로 나눈다! + 90도 회전하기 
				rotate(x,y,L,size); //시작 좌표 가지고 회전 
				
				y+=L;
				if(y>=size) { //마지막 위치까지 왔으면
					y=0; //y 0으로 만들고
					x+=L; //다음 행
				}
				if(x>=size) break;  //행까지 다돌았으면 끝	
			}
			nearIce(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) {
					group=Math.max(group, bfs(i,j,size));
				}
			}
		}
		
	}
	private static int bfs(int x, int y, int size) {
		int cnt=1;
		Queue <int[]> queue= new LinkedList<>();
		queue.offer(new int[] {x,y});
		visited[x][y]=true;
		
		while(!queue.isEmpty()) {
			int []point=queue.poll();
			
			for(int d=0; d<4; d++) {
				int nx=point[0]+dx[d];
				int ny=point[1]+dy[d];
				
				if(nx<0 || ny<0 || ny>=size || nx>=size || map[nx][ny]==0 || visited[nx][ny]) continue;
				cnt++;
				queue.offer(new int[] {nx,ny});
				visited[nx][ny]=true;
			}
		}
		
		return cnt;
	}
	private static void nearIce(int size) {
		for(int i=0; i<size; i++) {
			for(int j=0; j<size; j++) {
				int ice=copyMap[i][j];
				int cnt=0;
				
				if(ice==0) {
					map[i][j]=0;
					continue;
				}
				
				for(int d=0; d<4; d++) {
					int nx=i+dx[d];
					int ny=j+dy[d];
					
					if(nx<0 || ny<0 || nx>=size || ny>=size || copyMap[nx][ny]==0) continue;
					cnt++;
				}
				
				//인접한개 3개이상이면 그냥 넣어주고 아니면 --해줌
				if(cnt<3) map[i][j]=ice-1;
				else map[i][j]=ice;
			}
		}
		
		
	}
	private static void rotate(int x, int y, int l, int size) {
		int tmpy=0;
		for(int i=x; i<x+l; i++) {
			int tmpx=x;
			for(int j=y; j<y+l; j++) {
				copyMap[tmpx][y+l-1-tmpy]=map[i][j];
				
				tmpx++;
			}
			tmpy++;
		}
	}

}

소요시간 : 1시간 15분

 

로직을 살펴보면

 

 

1. 배열을 2^L x 2^L로 나누어서 90도 회전시켜준다. (원래 map에서 -> copyMap 으로 90도 회전한 값을 바로 넣어줌)

 - 배열을 90도로 돌리는 방법은 쉽습니다!

 

1행 값을 3열에 넣고

2행 값을 2열에 넣고

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

 

그리고 2^L 로 나누는 방법은 0,0에서 시작해 y값을 L만큼 늘려주고 y값이 끝나면 x값을 늘려주는 방식으로 했습니다.

2. 각 칸을 돌면서 인접한 4개의 칸 중 3개 이상이 얼음을 가지고 있는지 확인해줍니다. 

-만약 얼음을 가진 인접한 칸이 3개 미만이라면 자신의 칸에 얼음을 -1 해줍니다.

-1번에서 copyMap에 값을 집어넣었는데 이 값들을 이용해서 다시 map에 작성을 해줍니다.

-맵을 2개 사용하는 이유는 맵 1개를 이용하면 참조해야 하는 다른 칸들의 값이 바뀌어서 정확한 값을 낼 수가 없습니다.

 

 

 

3. 마지막으로 각 칸을 돌면서 얼음을 더해주고 bfs를 통해 가장 큰 덩어리를 찾아줍니다.

 

 

끝~