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

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

 

쉽게 풀 수 있는 문제인 듯 하다!

하지만 코드가 참 길다 하하

 

 

 

N의 값에 따라 전체 grid 크기를 계산하여 값 넣어준다.

 

일단 배열을 격자를 나눴을 때 

여기!

시작점을 기준으로 배열을 찾았다.

 

찾은 배열은 

->

->

->

순서로 1차원 배열(numArr)에 담는다.

그리고

방향으로 numArr 값을 넣는 방식으로

배열을 회전시켰다.

 

그러고 나면 그냥 배열 순회하면서 얼음 인접 2개 이하인 얼음들 -1씩 해준다. ( 나는 처음에 0일 때도 -1 해서 답 잘못 나왔었다. ㅋㅋㅋ)

 

그리고 단순 dfs 로 blob의 최대 크기를 찾으면 끝~~!

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

public class Main {
	static int N=1, Q, blobSize, MAX = 0;
	static int[][] grid;
	static int[] LArr;
	
	public static void main(String[] args) throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());
		int n = Integer.parseInt(st.nextToken());
		Q = Integer.parseInt(st.nextToken());
		LArr = new int[Q];
		
		for (int i = 0; i < n; i++) {
			N *= 2;
		}
		
		grid = new int[N][N];
		
		for (int i = 0; i < N; i++) {
			st = new StringTokenizer(br.readLine());
			for (int j = 0; j < N; j++) {
				grid[i][j] = Integer.parseInt(st.nextToken());
			}
		}
		
		st = new StringTokenizer(br.readLine());
		for (int i = 0; i < Q; i++) {
			LArr[i] = Integer.parseInt(st.nextToken());
		}
		
		solve();
		System.out.println(getSumIce());
		
		for (int i = 0; i < N; i++) {
			for (int j = 0; j < N; j++) {
				if(grid[i][j] > 0) {
					visited = new boolean[N][N];
					blobSize = 0;
					getBlobMaxSize(i, j);
					if(MAX < blobSize) MAX = blobSize;
				}
			}
		}
		System.out.println(MAX);
		
	} // main
	
	static void solve() {
		
		for(int l : LArr) {
			int L = 1;
			for (int i = 0; i < l; i++) {
				L *= 2;
			}
			int[] numArr = new int[L*L];
			for (int i = 0; i <= N-L; i+=L) {
				for (int j = 0; j <= N-L; j+=L) {
					int idx = 0;
					int r = i+L-1, c = j;
					while(true) {
						numArr[idx++] = grid[r][c];
						if(r == i && c == j+L-1) break;
						r--;
						if(r < i) {
							r = i+L-1;
							c++;
						}
					}
					
					idx = 0;
					for (int i2 = i; i2 < i+L; i2++) {
						for (int j2 = j; j2 < j+L; j2++) {
							grid[i2][j2] = numArr[idx++];
						}
					}
					
				} // j
			} // i
			// 회전끝
			
			minusIce();
		} // for
		
	} // solve
	
	static int[][] dir = new int[][] { { 0, -1 }, { 1, 0 }, { 0, 1 }, { -1, 0 } };
	static void minusIce() {
		List<int[]> list = new ArrayList<>();
		
		for (int i = 0; i < N; i++) {
			for (int j = 0; j < N; j++) {
				int adjCnt = 4;
				for (int d = 0; d < 4; d++) {
					int x = i+dir[d][0], y = j+dir[d][1];
					if(!isInBound(x, y)) adjCnt--;
					else if(grid[x][y] < 1) adjCnt--;
				} // d
				if(adjCnt <= 2) list.add(new int[] {i, j});
			} // j
		} // i
		
		for(int[] pos : list) {
			if(grid[pos[0]][pos[1]] > 0)
				grid[pos[0]][pos[1]]--;
		}
	} // minusIce
	
	static boolean[][] visited;
	static void getBlobMaxSize(int x, int y) {
		visited[x][y] = true;
		if(grid[x][y] > 0) blobSize++;
		else return;
		
		for (int d = 0; d < 4; d++) {
			int nx = x+dir[d][0], ny = y+dir[d][1];
			if(isInBound(nx, ny) && !visited[nx][ny])
				getBlobMaxSize(nx, ny);
		}
		
	} // getBlobMaxSize
	
	static boolean isInBound(int x, int y) {
		if (x < 0 || x >= N || y < 0 || y >= N)
			return false;
		return true;
	}
	
	static int getSumIce() {
		int sum = 0;
		for (int i = 0; i < N; i++) {
			for (int j = 0; j < N; j++) {
				sum += grid[i][j];
			}
		}
		return sum;
	}
	
	static void printArr() {
		for (int i = 0; i < N; i++) {
			for (int j = 0; j < N; j++) {
				System.out.print(grid[i][j] + " ");
			}
			System.out.println();
		}
	}
	
}