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

문제 설명

• 마법을 시전할 때마다 격자의 배열이 달라집니다.
• 마법을 시전한 후 3개 이상의 얼음에 둘러쌓여있지 않으면 해당 칸은 1만큼 녹습니다.
  • 얼음은 동시에 녹습니다.
  • [[0,0,0,0,0],[0,0,1,0,0],[0,1,99,1,0],[0,0,1,0,0],[0,0,0,0,0]]이 주어졌을 때 1들이 녹은 영향으로 인해 99가 녹지 상황은 발생하지 않습니다.

접근법

• 2^L만큼씩 그룹으로 묶어 회전시켜야 합니다.
  • 부분배열을 회전시키는 TurnClockWise 메서드를 만들었습니다.
  • 각 부분배열의 시작점은 powL만큼씩 차이를 가집니다.
    • 
• 덩어리의 크기를 확인하기 위해 BFS를 사용했습니다.

pseudocode

main(){
	for(Q번 마법을 시전합니다){
    	MoveBoard(powN,powL) // powLxpowL크기 묶음의 부분배열을 각각 회전시킵니다.
        MeltingIce(); // 조건을 충족하지 못한 얼음을 녹입니다.
    }
    남아있는 얼음의 합을 구합니다.
    BFS로 가장 큰 덩어리가 차지하는 칸의 개수를 구합니다.
}


MoveBoard(){
	for(0부터 powN까지 powL크기만큼씩 움직이는 2차원 배열 탐색을 하면서){
		TurnClockWise();
    }
}

TurnClockWise(){
	부분배열의 값을 더미배열에 새롭게 담는 방식으로 시계방향 화전을 구현합니다.
}

MeltingIce(){
    if(주변에 얼음이 3개 이상 없으면){
    	녹여야 할 얼음 배열에 추가합니다.
        // 여기서 곧바로 얼음을 녹이지 않습니다.
    }    
    for(녹아야 할 얼음을 하나씩 꺼내면서){
    	해당 좌표의 얼음을 1만큼 녹입니다.
    }
}

SurroundCheck(){	
	for(4방탐색을 진행하면서){
    	if(해당 칸이 보드를 벗어나지 않았고 얼음이 존재한다면){
        	cnt를 1 증가시킵니다 // cnt는 해당 좌표 4방에 몇 개의 얼음이 존재하는지를 나타냅니다.
        }
    }
    
}

정답

import java.util.*;

public class Main {
	static int[][] board;
	final static int[] dx = { 1, 0, -1, 0 };
	final static int[] dy = { 0, -1, 0, 1 };
	static int MaxScore = 0;

	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		int N = sc.nextInt();
		int Q = sc.nextInt();
		int powN = (int) Math.pow(2, N);
		board = new int[powN][powN];

		for (int i = 0; i < board.length; i++) {
			for (int j = 0; j < board.length; j++) {
				board[i][j] = sc.nextInt();
			}
		}

		for (int i = 0; i < Q; i++) { // Q번의 마법을 시전합니다.
			int L = sc.nextInt();
			int powL = (int) Math.pow(2, L); 
			MoveBoard(powN, powL); // 얼음판을 회전시킵니다.
			MeltingIce(); // 일부 얼음이 녹습니다.

		}

		// 남아있는 얼음의 합
		int cnt = 0;
		for (int i = 0; i < board.length; i++) {
			for (int j = 0; j < board.length; j++) {
				cnt += board[i][j];
			}
		}
		System.out.println(cnt);
		
		// 가장 큰 덩어리가 차지하는 칸의 개수
		for (int i = 0; i < board.length; i++) {
			for (int j = 0; j < board.length; j++) {
				if (board[i][j] == 0)
					continue;
				int[] temp = { i, j };
				MaxScore = Math.max(MaxScore, BFS(temp));
			}
		}
		System.out.println(MaxScore);

	}
	
    // 각 배열의 시작점만 구한다고 생각하는 게 편합니다.
    // 각 배열의 시작점은 powL씩만큼의 차이로 나타납니다.
	public static void MoveBoard(int powN, int powL) {
		for (int i = 0; i < powN; i += powL) {
			for (int j = 0; j < powN; j += powL) {
				TurnClockWise(i, j, i + powL, j + powL);
			}
		}
	}

	// 하나의 배열을 시계방향으로 회전시키는 메서드 입니다.
	public static void TurnClockWise(int startX, int startY, int endX, int endY) {
		int[][] dummyBoard = new int[endX - startX][endY - startY];
		for (int i = 0; i < dummyBoard.length; i++) {
			for (int j = 0; j < dummyBoard.length; j++) {
            	// dummyBoard[j][duumyBoard.length-1-i]는 더미배열의 우측에서 좌측으로, 상단에서 하단으로 값을 채워나갑니다.
            	// dummyBoard의 인덱스를 기준으로 i,j를 세팅했기 때문에 실제 board에서의 값을 뽑을 때에는 startX,startY만큼의 좌표 보정을 해줘야 합니다.
				dummyBoard[j][dummyBoard.length - 1 - i] = board[i + startX][j + startY]; 
			}
		}

		for (int i = startX; i < endX; i++) {
			for (int j = startY; j < endY; j++) {
				board[i][j] = dummyBoard[i - startX][j - startY];
			}
		}

	}
    
	// 자신 주위에 얼음이 몇 개 있는지 확인합니다.
	public static int SurroundCheck(int x, int y) {
		int cnt = 0;
		for (int d = 0; d < 4; d++) {
			int nx = x + dx[d];
			int ny = y + dy[d];
			if (0 <= nx && nx < board.length && 0 <= ny && ny < board.length && board[nx][ny] != 0)
				cnt++;
		}
		return cnt;
	}
	
	public static void MeltingIce(){
		// 줄어드는 얼음을 확인합니다.
		// 배열을 탐색하면서 실시간으로 얼음이 줄면 다음 얼음에도 영향을 받습니다.
		// 줄어들어야 할 얼음을 lst에 담고 모든 탐색이 끝난 뒤 줄입니다.
		List<int[]> lst = new ArrayList<int[]>(); 
		for (int x = 0; x < board.length; x++) {
			for (int y = 0; y < board.length; y++) {
				// 얼음이 없는 칸은 확인할 필요가 없습니다.
				if (board[x][y] == 0)
					continue;
				// 주변에 얼음이 3개이상 없으면 해당칸은 줄어듭니다.
				if (SurroundCheck(x, y) < 3) {
					int[] temp = { x, y };
					lst.add(temp);
				}
			}
		}
		
		// 줄어들어야 할 얼음들을 실제로 줄입니다.
		for (int z = 0; z < lst.size(); z++) {
			int[] temp = lst.get(z);
			board[temp[0]][temp[1]] -= 1;
		}		
		
	}

	public static int BFS(int[] start) {
		boolean[][] v = new boolean[board.length][board.length];
		Queue<int[]> q = new LinkedList<int[]>();
		q.add(start);
		int score = 1;
		while (q.size() != 0) {
			int[] val = q.poll();
			v[val[0]][val[1]] = true;
			for (int d = 0; d < 4; d++) {
				int nx = val[0] + dx[d];
				int ny = val[1] + dy[d];
				if (0 <= nx && nx < board.length && 0 <= ny && ny < board.length && !v[nx][ny] && board[nx][ny] != 0) {
					int[] temp = { nx, ny };
					q.add(temp);
					v[nx][ny] = true;
					score++;
				}
			}
		}
		return score;
	}

}