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

Java

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

문제

접근 방법

1. 2^L 단위로 배열을 나눈다.
2. 각 단위 내부의 배열을 시계방향으로 90도 회전한다.
3. 모든 칸을 기준으로 각각 인접한 얼음이 3개 미만인 얼음의 양을 1 줄인다.

출력

1. 얼음의 수를 센다.
2. 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);
    }
}

총평

후기

개선할 점