[Baekjoon] 마법사 상어와 파이어스톰

👀 문제 설명

문제

마법사 상어는 파이어볼과 토네이도를 조합해 파이어스톰을 시전할 수 있다. 오늘은 파이어스톰을 크기가 2N × 2N인 격자로 나누어진 얼음판에서 연습하려고 한다. 위치 (r, c)는 격자의 r행 c열을 의미하고, A[r][c]는 (r, c)에 있는 얼음의 양을 의미한다. A[r][c]가 0인 경우 얼음이 없는 것이다.

파이어스톰을 시전하려면 시전할 때마다 단계 L을 결정해야 한다. 파이어스톰은 먼저 격자를 2L × 2L 크기의 부분 격자로 나눈다. 그 후, 모든 부분 격자를 시계 방향으로 90도 회전시킨다. 이후 얼음이 있는 칸 3개 또는 그 이상과 인접해있지 않은 칸은 얼음의 양이 1 줄어든다. (r, c)와 인접한 칸은 (r-1, c), (r+1, c), (r, c-1), (r, c+1)이다. 아래 그림의 칸에 적힌 정수는 칸을 구분하기 위해 적은 정수이다.

마법사 상어는 파이어스톰을 총 Q번 시전하려고 한다. 모든 파이어스톰을 시전한 후, 다음 2가지를 구해보자.

1. 남아있는 얼음 A[r][c]의 합
2. 남아있는 얼음 중 가장 큰 덩어리가 차지하는 칸의 개수

얼음이 있는 칸이 얼음이 있는 칸과 인접해 있으면, 두 칸을 연결되어 있다고 한다. 덩어리는 연결된 칸의 집합이다.

 

입력

첫째 줄에 N과 Q가 주어진다. 둘째 줄부터 2N개의 줄에는 격자의 각 칸에 있는 얼음의 양이 주어진다. r번째 줄에서 c번째 주어지는 정수는 A[r][c] 이다.

마지막 줄에는 마법사 상어가 시전한 단계 L1, L2, ..., LQ가 순서대로 주어진다.

 

출력

첫째 줄에 남아있는 얼음 A[r][c]의 합을 출력하고, 둘째 줄에 가장 큰 덩어리가 차지하는 칸의 개수를 출력한다. 단, 덩어리가 없으면 0을 출력한다.

 

제한

• 2 ≤ N ≤ 6
• 1 ≤ Q ≤ 1,000
• 0 ≤ A[r][c] ≤ 100
• 0 ≤ Li ≤ N

 

예제 입력 1

3 1

1 2 3 4 5 6 7 8

8 7 6 5 4 3 2 1

1 2 3 4 5 6 7 8

8 7 6 5 4 3 2 1

1 2 3 4 5 6 7 8

8 7 6 5 4 3 2 1

1 2 3 4 5 6 7 8

8 7 6 5 4 3 2 1

1

 

예제 출력 1

284

64

 

예제 입력 2

3 2

1 2 3 4 5 6 7 8

8 7 6 5 4 3 2 1

1 2 3 4 5 6 7 8

8 7 6 5 4 3 2 1

1 2 3 4 5 6 7 8

8 7 6 5 4 3 2 1

1 2 3 4 5 6 7 8

8 7 6 5 4 3 2 1

1 2

 

예제 출력 2

280

64

 

예제 입력 3

3 5

1 2 3 4 5 6 7 8

8 7 6 5 4 3 2 1

1 2 3 4 5 6 7 8

8 7 6 5 4 3 2 1

1 2 3 4 5 6 7 8

8 7 6 5 4 3 2 1

1 2 3 4 5 6 7 8

8 7 6 5 4 3 2 1

1 2 0 3 2

 

예제 출력 3

268

64

 

예제 입력 4

3 10

1 2 3 4 5 6 7 8

8 7 6 5 4 3 2 1

1 2 3 4 5 6 7 8

8 7 6 5 4 3 2 1

1 2 3 4 5 6 7 8

8 7 6 5 4 3 2 1

1 2 3 4 5 6 7 8

8 7 6 5 4 3 2 1

1 2 0 3 2 1 2 3 2 3

 

예제 출력 4

248

62

 

예제 입력 5

3 10

1 2 3 4 5 6 7 8

8 7 6 5 4 3 2 1

1 2 3 4 5 6 7 8

8 7 6 5 4 3 2 1

1 2 3 4 5 6 7 8

8 7 6 5 4 3 2 1

1 2 3 4 5 6 7 8

8 7 6 5 4 3 2 1

1 2 3 1 2 3 1 2 3 1

 

예제 출력 5

246

60

 

예제 입력 6

3 10

1 0 3 4 5 6 7 0

8 0 6 5 4 3 2 1

1 2 0 4 5 6 7 0

8 7 6 5 4 3 2 1

1 2 3 4 0 6 7 0

8 7 0 5 4 3 2 1

1 2 3 4 5 6 7 0

0 7 0 5 4 3 2 1

1 2 3 1 2 3 1 2 3 1

 

예제 출력 6

37

9

 

✍🏻풀이

구현 문제이다.

 

3 단계로 나눠 풀면 된다.

step 1. 격자를 2^L x 2^L 크기의 부분 격자로 나눈다.

step 2. 부분 격자를 시계 방향으로 90도 회전시킨다.

step 3. 얼음이 있는 칸 3개 또는 그 이상과 인접해있지 않은 칸은 얼음의 양이 1 줄어든다.

 

step 1과 step 2는 divideAndRotate라는 메소드로, step 3는 melt라는 메소드를 따로 만들었다.

melt라는 메소드에서 얼음이 있는 칸 3개 또는 그 이상과 인접해있지 않은 칸이라는 말은, 어떤 위치에서 인접한 위치들을 봤을 때, 얼음이 있는 칸이 2개 이하라는 말과 같다.

-> 이거 너무 설명을 헷갈리게 해둠.. 열받..ㅇ..ㅏ..

 

코드

package boj;

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

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

public class BOJ_20058 {
	
	private static int N, Q, row, partRow;
	private static int[][] A;
	private static int[] dx = { -1, 1, 0, 0 };
	private static int[] dy = { 0, 0, -1, 1 };
	private static Queue<int[]> queue = new LinkedList<>();
	private static boolean[][] visited;
	private static int maxMass = 0;
	
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
		
		// input
		StringTokenizer st = new StringTokenizer(br.readLine());
		
		N = Integer.parseInt(st.nextToken());
		Q = Integer.parseInt(st.nextToken());
		row = (int) Math.pow(2, N);
		A = new int[row][row];
		visited = new boolean[row][row];
		
		for (int i = 0; i < row; i++) {
			st = new StringTokenizer(br.readLine());
			
			for (int j = 0; j < row; j++) {
				A[i][j] = Integer.parseInt(st.nextToken());
			}
		}
		
		st = new StringTokenizer(br.readLine());
		for (int i = 0; i < Q; i++) {
			int L = Integer.parseInt(st.nextToken());
			partRow = (int) Math.pow(2, L);
			
			for (int r = 0; r < row; r += partRow) {
				for (int c = 0; c < row; c += partRow) {
					divideAndRotate(L, r, c); // step 1 & 2
				}
			}
			
			// step 3
			melt();
		}
		
		// output
		int ans = 0;
		for (int r = 0; r < row; r++) {
			for (int c = 0; c < row; c++) {
				ans += A[r][c];
			}
		}
		for (int r = 0; r < row; r++) {
			for (int c = 0; c < row; c++) {
				if (A[r][c] > 0 && !visited[r][c]) {
					getMaxMass(r, c);
				}
			}
		}
		
		bw.write(ans + "\n" + maxMass + "\n");
		
		bw.flush();
		bw.close();
	}
	
	// step 1 & 2
	private static void divideAndRotate(int L, int r, int c) {
		int[][] part = new int[partRow][partRow];
		int[][] newPart = new int[partRow][partRow];
		
		for (int i = r; i < r + partRow; i++) {
			for (int j = c; j < c + partRow; j++) {
				part[i - r][j - c] = A[i][j];
			}
		}
		
		for (int j = partRow - 1; j >= 0; j--) {
			for (int i = 0; i < partRow; i++) {
				newPart[i][j] = part[partRow - 1 - j][i];
			}
		}
		
		for (int i = r; i < r + partRow; i++) {
			for (int j = c; j < c + partRow; j++) {
				A[i][j] = newPart[i - r][j - c];
			}
		}
	}

	// step 3
	private static void melt() {
		for (int i = 0 ; i < row; i++) {
			for (int j = 0; j < row; j++) {
				int cnt = 0;
				for (int dir = 0; dir < 4; dir++) {
					int nextR = i + dx[dir];
					int nextC = j + dy[dir];
						
					if (nextR < 0 || nextR >= row || nextC < 0 || nextC >= row) continue;
						
					if (A[nextR][nextC] > 0) cnt++;
				}
				
				if (cnt < 3 && A[i][j] > 0) queue.offer(new int[] { i, j });
			}
		}
		
		while (!queue.isEmpty()) {
			int[] cur = queue.poll();
			
			A[cur[0]][cur[1]]--;
		}
	}
	
	private static void getMaxMass(int r, int c) {
		visited[r][c] = true;
		queue.offer(new int[] { r, c });

		int mass = 1;
		while (!queue.isEmpty()) {
			int[] cur = queue.poll();
			
			for (int dir = 0; dir < 4; dir++) {
				int nextR = cur[0] + dx[dir];
				int nextC = cur[1] + dy[dir];
				
				if (nextR < 0 || nextR >= row || nextC < 0 || nextC >= row) continue;
				
				if (A[nextR][nextC] > 0 && !visited[nextR][nextC]) {
					visited[nextR][nextC] = true;
					queue.offer(new int[] { nextR, nextC });
					mass++;
				}
			}
		}
		
		maxMass = Math.max(maxMass, mass);
	}
}