문제

BOJ 20058: 마법사 상어와 파이어스톰 https://www.acmicpc.net/problem/20058

풀이

조건

• 크기가 2^N × 2^N인 격자로 나누어진 얼음판에서 수행한다.
• 위치 (r, c)는 격자의 r행 c열을 의미하고, A[r][c]는 (r, c)에 있는 얼음의 양을 의미한다.
• A[r][c]가 0인 경우 얼음이 없는 것이다.
• 파이어스톰을 시전하려면 시전할 때마다 단계 L을 결정해야 한다.
  • 먼저 격자를 2^L × 2^L 크기의 부분 격자로 나눈다.
  • 모든 부분 격자를 시계 방향으로 90도 회전시킨다.
  • 얼음이 있는 칸 3개 또는 그 이상과 인접해있지 않은 칸은 얼음의 양이 1 줄어든다.
    • 즉, 주위에 얼음이 있는 칸이 3개 미만이면 현재 칸의 얼음 양이 1 줄어든다.
  • (r, c)와 인접한 칸은 (r-1, c), (r+1, c), (r, c-1), (r, c+1)이다.

풀이 순서

1. 회전할 덩어리 격자를 나눈다.
   • 격자 한 변의 길이를 구한다.
   • 회전시킬 덩어리의 가장 앞 쪽 좌표(가장 왼쪽, 위)에서 회전 메소드를 호출한다.
     • for문에서 L크기만큼 증가시키면 된다.
2. 90도 시계방향으로 회전시킨다.
   • 격자가 90도 회전하므로 일정한 규칙을 찾는다.
   • temp 배열이 회전 이후의 상태, map 배열이 회전 이전의 원본 배열이다.
   • temp[x + i][y + j] = map[x + L - 1 - j][y + i];
   • 위의 과정은 그림을 그려 확인했다.
3. 위의 과정을 Q번 반복한다.
4. BFS를 사용하여 답을 찾는다.

코드

package Main;

import java.util.*;
import java.io.*;

public class Main {
    
	static int N, Q;
	static int[][] map;
	
	static int[] arrL;
	
	static int mapSize;
	
	static int[] dx = {1, -1, 0 ,0};
	static int[] dy = {0, 0, 1 ,-1};
	
	static int iceSum;
	static int biggestSum;
	
    public static void main(String[] args) throws IOException {
    	BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    	
    	StringTokenizer st = new StringTokenizer(br.readLine(), " ");
    	N = Integer.parseInt(st.nextToken()); // 맵 크기에 사용될 변수
    	Q = Integer.parseInt(st.nextToken()); // 단계 횟수
    		
    	mapSize = (int)Math.pow(2, N); // 사용할 map의 크기
    	map = new int[mapSize + 1][mapSize + 1];
    	
    	for(int i=1; i<=mapSize; i++) {
    		st = new StringTokenizer(br.readLine(), " ");
    		for(int j=1; j<=mapSize; j++) {
    			map[i][j] = Integer.parseInt(st.nextToken());
    		}
    	}
    	
    	arrL = new int[Q+1];
    	st = new StringTokenizer(br.readLine(), " ");
    	for(int i=1; i<arrL.length; i++) {
    		arrL[i] = Integer.parseInt(st.nextToken());
    	}
    	
    	// 이동 명령 수행
    	for(int i=1; i<arrL.length; i++) {
    		// 회전할 덩어리를 나눔
    		map = divide(arrL[i]);
    		// 얼음을 녹임
    		map = melt();
    	}
    	
    	iceSum = 0; // 전체 얼음의 양
    	biggestSum = 0; // 가장 큰 얼음 덩어리의 크기
    	
    	// 정답 찾기
    	answer();
    	
    	System.out.println(iceSum);
    	System.out.println(biggestSum);
    	
    }
    
    // 회전 시킬 덩어리를 나누는 메소드
    static int[][] divide(int L) {
    	int[][] temp = new int[mapSize + 1][mapSize+ 1];
    	L = (int)Math.pow(2, L); // 덩어리 한 변의 크기
    	
    	// L 만큼 증가시키며 회전
    	for(int i=1; i<=mapSize; i+=L) {
    		for(int j=1; j<=mapSize; j+=L) {
    			rotate(i, j, L, temp);
    		}
    	}
    	
    	return temp;
    }
    
    // 덩어리를 회전시키는 메소드
    static void rotate(int x, int y, int L, int[][] temp) {
    	/*
    	 * x: 회전 시작할 좌표(행)
    	 * y: 회전 시작할 좌표(열)
    	 * L: 회전 덩어리 한 변의 크기
    	 * temp: 복사해서 사용할 배열
    	 */
    	
    	// 회전시킴
    	for(int i=0; i<L; i++) {
    		for(int j=0; j<L; j++) {
    			temp[x + i][y + j] = map[x + L - 1 - j][y + i];
    		}
    	}
	
    }
    
    // 얼음을 녹이는 메소드
    static int[][] melt() {
    	// 복사 배열 생성
    	int[][] temp = new int[mapSize + 1][mapSize + 1];
    	for(int i=1; i<=mapSize; i++) {
    		for(int j=1; j<=mapSize; j++) {
    			temp[i][j] = map[i][j];
    		}
    	}
    	
    	for(int i=1; i<=mapSize; i++) {
    		for(int j=1; j<=mapSize; j++) {
    			int cnt = 0; // 주위에 얼음이 몇 개 있는지 나타낼 변수
    			
    			// 해당 좌표에 얼음이 없으면 넘어감
    			if(map[i][j] == 0) continue;
    			
    			// 4방향 탐색
    			for(int t=0; t<4; t++) {
    				int nx = i + dx[t];
    				int ny = j + dy[t];
    				// 범위 체크
    				if(nx < 1 || nx > mapSize || ny < 1 || ny > mapSize) continue;
    				// 탐색한 위치에 얼음이 있으면 cnt++
    				if(map[nx][ny] > 0) cnt++;
    			}
    			
    			// 4방향 중 얼음이 있는 위치의 갯수가 3 미만이면 해당 위치의 얼음 양을 -1
    			if(cnt < 3) {
    				temp[i][j]--;
    			}
    		}
    	}
    	
    	return temp;
    }
    
    // 답 찾는 메소드
    // BFS 사용
    static void answer() {
    	Queue<int[]> que = new LinkedList<>();
    	boolean[][] isVisited = new boolean[mapSize + 1][mapSize + 1];
    	
    	for(int i=1; i<=mapSize; i++) {
    		for(int j=1; j<=mapSize; j++) {
    			iceSum += map[i][j];
    			if(map[i][j] > 0 && !isVisited[i][j]) {
    				que.add(new int[] {i, j});
    				isVisited[i][j] = true;
    				int cnt = 1;
    				
    				while(!que.isEmpty()) {
    					int[] now = que.poll();
    					
    					int curX = now[0];
    					int curY = now[1];
    					
    					for(int t=0; t<4; t++) {
    						int nx = curX + dx[t];
    						int ny = curY + dy[t];
    						
    						if(nx < 1 || nx > mapSize || ny < 1 || ny > mapSize) continue;
    						
    						if(map[nx][ny] > 0 && !isVisited[nx][ny]) {
    							isVisited[nx][ny] = true;
    							que.add(new int[] {nx, ny});
    							cnt++;
    						}
    					}
    				}
    				
    				biggestSum = Math.max(biggestSum, cnt);
    			}
    		}
    	}
    	
    }
 
}

정리

• 회전 시키는 메소드를 구현하는 데 시간이 오래 걸렸다.
• 규칙을 찾아 구현하는 것이 중요했다.