백준 20058 - 마법사 상어와 파이어스톰
Updated:
Java
20058 번 - 마법사 상어와 파이어스톰
문제
접근 방법
- 2^L 단위로 배열을 나눈다.
- 각 단위 내부의 배열을 시계방향으로 90도 회전한다.
- 모든 칸을 기준으로 각각 인접한 얼음이 3개 미만인 얼음의 양을 1 줄인다.
출력
- 얼음의 수를 센다.
- BFS를 사용한다.
- (0,0) 부터 탐색하여 BFS를 방문한다.
- 각 칸을 방문할 때마다 cnt를 올려 최대 얼음의 크기를 구한다.
코드
import java.util.*;
import java.io.*;
public class Main {
static int n, m, q, result;
static int[][] board, temp;
static boolean[][] vis;
public static void main(String[] args) throws IOException {
System.setIn(new FileInputStream("res/mainInput.txt")); //제출 할 때 주석해야함
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer stk = new StringTokenizer(br.readLine());
m = stoi(stk.nextToken());
q = stoi(stk.nextToken());
n = (int)Math.pow(2, m);
board = new int[n][n];
temp = new int[n][n];
vis = new boolean[n][n];
for(int i = 0; i < n; i++) {
stk = new StringTokenizer(br.readLine());
for(int j = 0; j < n; j++) {
board[i][j] = stoi(stk.nextToken());
}
}
int l;
stk = new StringTokenizer(br.readLine());
while(q-- != 0) {
l = stoi(stk.nextToken());
turnBoard(l);
burnIce();
}
System.out.println(cntIce());
for(int i = 0; i < n; i++) {
for(int j = 0; j < n; j++) {
if(board[i][j] >= 1) {
result = Math.max(BFS(i,j), result);
}
}
}
System.out.println(result);
br.close();
}
private static int cntIce() {
int rst = 0;
for(int i = 0; i < n; i++) {
for(int j = 0; j < n; j++) {
rst += board[i][j];
}
}
return rst;
}
private static void turnBoard(int l) {
l = (int)Math.pow(2, l);
for(int i = 0; i < n; i += l) {
for(int j = 0; j < n; j += l) {
turnPart(i,j,l);
}
}
}
static int[] dy = {-1,1,0,0};
static int[] dx = {0,0,-1,1};
private static void burnIce() {
int ny,nx,cnt;
for(int y = 0; y < n; y++) {
for(int x = 0; x < n; x++) {
cnt = 4;
for(int i = 0; i < 4; i++) {
ny = y + dy[i];
nx = x + dx[i];
if(!isIn(ny,nx) || temp[ny][nx] <= 0) {
cnt--;
}
}
if(cnt < 3 && board[y][x] >= 1) {
board[y][x]--;
}
}
}
}
private static void turnPart(int y, int x, int len) {
int pivot = len - 1;
for(int i = 0; i < len; i++) {
for(int j = 0; j < len; j++) {
temp[y + i][x + j] = board[y + pivot - j][x + i];
}
}
for(int i = 0; i < len; i++) {
for(int j = 0; j < len; j++) {
board[y + i][x + j] = temp[y + i][x + j];
}
}
}
private static int BFS(int y, int x) {
Queue<int[]> queue = new LinkedList<int[]>();
int cnt = 1;
queue.add(new int[] {y,x});
int ny,nx;
int[] q;
vis[y][x] = true;
while(!queue.isEmpty()) {
q = queue.poll();
y = q[0];
x = q[1];
for(int i = 0; i < 4; i++) {
ny = y + dy[i];
nx = x + dx[i];
if(isIn(ny,nx) && board[ny][nx] >= 1 && !vis[ny][nx]) {
vis[ny][nx] = true;
queue.add(new int[] {ny,nx});
cnt++;
}
}
}
return cnt;
}
// 주어진 범위 안에 있는가
public static boolean isIn(int y, int x){
if(y < 0 || y >= n || x < 0 || x >= n)
return false;
return true;
}
static int stoi(String str) {
return Integer.parseInt(str);
}
}