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

문제

• BOJ 20058
• 문제의 저작권은 Baekjoon Online Judge에 있습니다.

접근방식

1. 시계 방향 90도 회전
2^N*2^N으로 격자를 나눈 후 90도 회전한 결과를 tmp배열에 넣는다.
2. 얼음 줄이기
배열 전체를 돌면서 상화좌우 탐색하여 인접한 칸에 얼음이 있으면 cnt를 증가시킨다.
모든 탐색 후 cnt가 3개 미만이면 check배열에 true표시한다. 이때 주의할 점은 탐색하면서 얼음을 바로 줄이면 안된다.
다음에 검사할 배열값에도 영향을 주기 때문에 모든 탐색이 끝난 후에 다시 for문을 돌면서 check에 true표시해준 값의 얼음의 양을 하나 줄여야 한다.
3. 합 구하기
모든 시전이 끝나면 남아있는 얼음을 구하기 위해 배열값을 누적합한다.
4. 가장 큰 덩어리 구하기 가장 큰 덩어리를 만들기 위해서는 연결된 그룹을 탐색해야 하므로 bfs탐색을 해서 가장 큰 덩어리의 칸 개수를 구한다.

2번에서 얼음을 바로 줄여서 ‘틀렸습니다’가 나왔다. 틀리고 나서 깨달았다..이런 자잘한 실수를 줄여야할텐데ㅠㅠ

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.LinkedList;
import java.util.Queue;
import java.util.StringTokenizer;

public class Main {

	static int N, Q;
	static int[][] map, tmp;
	static int[][] dInfo = { { -1, 0 }, { 1, 0 }, { 0, -1 }, { 0, 1 } };
	static Queue<Point> queue;
	static boolean[][] visited;
	static boolean[][] checked;
	static int size;
	static int ans_sum;
	static int ans_max;

	static class Point {
		int x;
		int y;

		public Point(int x, int y) {
			this.x = x;
			this.y = y;
		}
	}

	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

		StringTokenizer st = new StringTokenizer(br.readLine());
		N = Integer.parseInt(st.nextToken());
		Q = Integer.parseInt(st.nextToken());

		size = (int) Math.pow(2, N); // 한변의 길이
		map = new int[size][size];

		for (int i = 0; i < size; i++) {
			st = new StringTokenizer(br.readLine());
			for (int j = 0; j < size; j++) {
				map[i][j] = Integer.parseInt(st.nextToken());
			}
		} // End input

		st = new StringTokenizer(br.readLine());

		for (int q = 0; q < Q; q++) {
			int l = Integer.parseInt(st.nextToken()); // 분할 크기
			tmp = new int[size][size];

			// 1. 90도 회전
			for (int i = 0; i < size; i += (int) Math.pow(2, l)) {
				for (int j = 0; j < size; j += (int) Math.pow(2, l)) {
					rotate(i, j, (int) Math.pow(2, l));
				}
			}

			checked = new boolean[size][size];

			// 2. 얼음 줄이기
			for (int i = 0; i < size; i++) {
				for (int j = 0; j < size; j++) {
					int cnt = 0;
					if (map[i][j] == 0)
						continue;
					for (int d = 0; d < 4; d++) {
						int ni = i + dInfo[d][0];
						int nj = j + dInfo[d][1];

						if (ni >= 0 && ni < size && nj >= 0 && nj < size && map[ni][nj] > 0)
							cnt++;
					}
					if (cnt < 3)
						checked[i][j] = true;
				}
			}

			for (int i = 0; i < size; i++) {
				for (int j = 0; j < size; j++) {
					if (checked[i][j])
						map[i][j]--;
				}
			}
		} // End 시전

		// 3. 합 구하기
		for (int i = 0; i < size; i++) {
			for (int j = 0; j < size; j++) {
				if (map[i][j] <= 0)
					continue;
				ans_sum += map[i][j];
			}
		}

		// 4. 가장 큰 덩어리 구하기
		queue = new LinkedList<>();
		visited = new boolean[size][size];

		for (int i = 0; i < size; i++) {
			for (int j = 0; j < size; j++) {
				if (!visited[i][j] && map[i][j] > 0) {
					queue.add(new Point(i, j));
					visited[i][j] = true;
					bfs();
				}
			}
		}

		bw.write(ans_sum + "\n");
		bw.write(ans_max + "");
		bw.flush();
		bw.close();
		br.close();
	}

	private static void bfs() {
		int cnt = 1;

		while (!queue.isEmpty()) {
			Point p = queue.poll();

			for (int d = 0; d < 4; d++) {
				int ni = p.x + dInfo[d][0];
				int nj = p.y + dInfo[d][1];

				if (ni >= 0 && ni < size && nj >= 0 && nj < size && !visited[ni][nj] && map[ni][nj] > 0) {
					queue.add(new Point(ni, nj));
					visited[ni][nj] = true;
					cnt++;
				}
			}
		}
		ans_max = Math.max(ans_max, cnt);
	}

	private static void rotate(int x, int y, int length) {
		for (int i = 0; i < length; i++) { // 90도 회전
			for (int j = 0; j < length; j++) {
				tmp[j][length - i - 1] = map[x + i][y + j];
			}
		}

		for (int i = 0; i < length; i++) { // 원래 배열에 복사
			for (int j = 0; j < length; j++) {
				map[x + i][y + j] = tmp[i][j];
			}
		}
	}
}