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

 

상어가 점점 그 실체를 드러내고 있다;;
상어 시리즈는 대게 구현과 시뮬레이션을 주제로 다루고 있고, 이번 문제 역시 배열을 구획을 나눠 회전시키는 방법과 간단한 BFS을 이용하는 문제이다. (한마디로 한 문제에 여러 개념을 때려박은 느낌;;;)

구현은 간단하다.
1. 회전하는 함수를 구성하고
2. 얼음을 녹이고
3. 가장 큰 덩어리는 그냥 bfs로 찾는다.

이런문제 너무 싫...

www.acmicpc.net/problem/20058

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

 

package week8;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.LinkedList;
import java.util.Queue;
import java.util.StringTokenizer;

public class Day3BOJ20058 {

	static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
	static StringTokenizer st;
	
	static int n,q,ans1,ans2;
	static int[] l;
	static int[][] map;
	static boolean[][] c;
	static int[] dy = {-1,1,0,0};
	static int[] dx = {0,0,-1,1};
	static class Pos{
		int y,x;
		public Pos(int y, int x) {
			this.y = y;
			this.x = x;
		}
	}
	
	private static void printMap() {
		for(int[] a : map) {
			System.out.println(Arrays.toString(a));
		}
		System.out.println();
	}
	
	private static void rotate(int y, int x, int size) {
		for(int i=0; i<size/2; i++) {
			for(int j=i; j<size-i-1; j++) {
				int tmp = map[y+i][x+j];
				map[y+i][x+j] = map[y+size-j-1][x+i];
				map[y+size-j-1][x+i] = map[y+size-i-1][x+size-j-1];
				map[y+size-i-1][x+size-j-1] = map[y+j][x+size-i-1];
				map[y+j][x+size-i-1] = tmp;
			}
		}
	}
	
	private static void bfs(int y, int x , int size) {
		Queue<Pos> q = new LinkedList<Pos>();
		int iceSize=0;
		q.offer(new Pos(y,x));
		c[y][x] = true;
		if(map[y][x]>0) iceSize++;
		
		while(!q.isEmpty()) {
			Pos cur = q.poll();
			for(int d=0; d<4; d++) {
				int ny = cur.y+dy[d];
				int nx = cur.x+dx[d];
				if(ny<0 || nx<0 || ny>=size || nx>=size || map[ny][nx]==0) continue;
				if(!c[ny][nx]) {
					c[ny][nx] = true;
					q.offer(new Pos(ny,nx));
					if(map[ny][nx]!=0) iceSize++;
				}
			}
		}
		ans2 = Math.max(ans2, iceSize);
	}
	
	public static void main(String[] args) throws IOException {
//		data Input
		st = new StringTokenizer(br.readLine());
		n = Integer.parseInt(st.nextToken());
		q = Integer.parseInt(st.nextToken());
		l = new int[q];
		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++) {
			l[k] = Integer.parseInt(st.nextToken());
		}
//		L rotation
		for(int ll : l) {
			// l size rotation
			int lSize = (int) Math.pow(2, ll);
			for(int i=0; i<size; i+=lSize) {
				for(int j=0; j<size; j+=lSize) {
					rotate(i,j,lSize);
				}
			}
			// melt
			Queue<Pos> melt = new LinkedList<Pos>();
			for(int i=0; i<size; i++) {
				for(int j=0; j<size; j++) {
					int ice = 0;
					for(int d=0; d<4; d++) {
						int ny = i+dy[d];
						int nx = j+dx[d];
						if(ny<0 || nx<0 || ny>=size || nx>=size) continue;
						if(map[ny][nx]>0) ice++;
					}
					if(ice<3 && map[i][j]>0) {
						melt.offer(new Pos(i,j));
					}
				}
			}
			while(!melt.isEmpty()) {
				Pos target = melt.poll();
				map[target.y][target.x]--;
			}
		}
//		System.out.println();
//		printMap();		
//		1번, ice Sum
		for(int i=0; i<size; i++) {
			for(int j=0; j<size; j++) {
				ans1+=map[i][j];
			}
		}

//		2번, biggest ice
		c = new boolean[size][size];
		for(int i=0; i<size; i++) {
			for(int j=0; j<size; j++) {
				if(!c[i][j] && map[i][j]!=0) {
					bfs(i,j,size);
				}
			}
		}
		
		System.out.println(ans1);
		System.out.println(ans2);
	}

}