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

[문제링크]

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

 

0. 단순 구현 + 그래프 탐색 문제

 

1. 주어진 l 값에 맞게, 각 칸을 회전시킨다

 

2. 다른 얼음과 2칸 이하로 맞닿은 칸들을 체크한다

 

3. 해당 칸들을 녹인다

 

4. 1~3 반복

 

5. 다 녹은 후 dfs를 실행, 가장 큰 덩어리의 크기를 찾는다

 

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

public class Main{
	static int[][]map;
	static boolean[][] chk;
	static int size;
	public static void main(String[] args)throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		
		StringTokenizer st = new StringTokenizer(br.readLine(), " ");
		int n = pint(st.nextToken());
		int m = pint(st.nextToken());
		size = 1<<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]=pint(st.nextToken());
			}
		}
		
		st = new StringTokenizer(br.readLine());
		for (int i = 0; i < m; i++) {
			int l = pint(st.nextToken());
			chk=new boolean[size][size];
			//돌리기
			divide(l);
			//녹일것찾기
			findMelt();
			//녹이기
			melt();
		}

		//dfs search
		chk=new boolean[size][size];
		int cntMax=0;
		for (int i = 0; i < size; i++) {
			for (int j = 0; j < size; j++) {
				if(!chk[i][j] && map[i][j]>0) {
					cntMax = Math.max(cntMax, dfs(i,j));
				}
			}
		}
		
		int sum=0;
		for (int i = 0; i < size; i++) {
			for (int j = 0; j < size; j++) {
				sum+=map[i][j];
			}
		}
		System.out.println(sum+"\n"+cntMax);
		
	}
	
	static int dfs(int x, int y) {
		int cnt=1;
		chk[x][y]=true;
		if(x>0 && !chk[x-1][y] && map[x-1][y]>0)cnt+=dfs(x-1,y);
		if(y>0 && !chk[x][y-1] && map[x][y-1]>0)cnt+=dfs(x,y-1);
		if(x<size-1 && !chk[x+1][y] && map[x+1][y]>0)cnt+=dfs(x+1,y);
		if(y<size-1 && !chk[x][y+1] && map[x][y+1]>0)cnt+=dfs(x,y+1);
		
		return cnt;
	}
	
	static void divide(int l) {
		int len = size / (1<<l);
		for (int i = 0; i < len; i++) {
			for (int j = 0; j < len; j++) {
				rotate(i*(1<<l), j*(1<<l), 1<<l);
			}
		}
	}
	
	static void findMelt() {
		for (int x = 0; x < size; x++) {
			for (int y = 0; y < size; y++) {
				int cnt=0;
				if(x>0 && map[x-1][y]>0)cnt++;
				if(y>0 && map[x][y-1]>0)cnt++;
				if(x<size-1 && map[x+1][y]>0)cnt++;
				if(y<size-1 && map[x][y+1]>0)cnt++;
				
				if(cnt<3 && map[x][y]>0) {
					chk[x][y]=true;
				}
			}
		}
	}
	static void melt() {
		for (int x = 0; x < size; x++) {
			for (int y = 0; y < size; y++) {
				if(chk[x][y])map[x][y]--;
			}
		}
	}
	
	static void rotate(int sx, int sy, int len) {
		if(len<=0)return;
		
		int tmp=len-1;
		int[] backup = new int[tmp];
		
		for (int i = 0; i < tmp; i++)backup[i]=map[sx][sy+i];
		
		for (int i = 0; i < tmp; i++) {
			map[sx][sy+tmp-1-i]=map[sx+i+1][sy];
		}
		for (int i = 0; i < tmp; i++) {
			map[sx+i+1][sy]=map[sx+tmp][sy+i+1];		
		}
		for (int i = 0; i < tmp; i++) {
			map[sx+tmp][sy+i+1]=map[sx+tmp-1-i][sy+tmp];
		}
		for (int i = 0; i < tmp; i++) {
			map[sx+tmp-1-i][sy+tmp]=backup[tmp-1-i];
		}
		rotate(sx+1,sy+1,len-2);
	}
	
	static int pint(String s) {
		return Integer.parseInt(s);
	}
}

결과 화면