[백준 20058] 마법사 상어와 파이어스톰 (JAVA)

🔰 문제

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

💡 접근방식

시뮬레이션, 배열 회전, dfs(bfs) 문제

1. 부분 배열별로 배열을 시계방향 90도 회전
2. 회전이 끝나면 인접 얼음이 3개 미만인 칸은 얼음 크기 -1 (4방 탐색)
3. 최종적으로 배열의 전체 얼음 합과 최대 덩어리 크기(그래프 탐색)

배열 회전이 어려웠던 문제이다.
처음엔 다음과 같은 방식으로 회전시키려 했다.

for (int l = 0; l < k / 2; l++) {
			for (int i = l; i < k - l; i++) {
				temp[x + l][y + i] = map[x + k - 1 - i][y + l]; // 위쪽 줄
				temp[x + i][y + k - 1 - l] = map[x + l][y + i]; // 오른쪽
				temp[x + k - 1 - l][y + i] = map[x + k - 1 - i][y + k - 1 - l]; // 아래
				temp[x + i][y + l] = map[x + k - 1 - l][y + i]; // 왼
			}
		}

코드를 보면 알겠지만 인덱스때문에 머리 아파 죽을 뻔 했다....🤔

💦 풀면서 실수, 놓친 점

1. 배열 90도 회전 방식을 착각함
   4X4 배열이 있을 때 2X2 부분 배열들을 시계방향으로 회전시키는 것으로 착각함
   배열 회전 방식에 대해 제대로 파악했어도 위에 접근방식에서 언급했듯이 구현하는데 시간이 오래 걸렸다.

🌟 시계방향 90도 회전 쉽게 하는 법

k= 2^L (부분배열 크기)

	private static void rotate(int x, int y, int k, int[][] copy) {

		for (int i = 0; i < k; i++) {
			for (int j = 0; j < k; j++) {
				map[x + j][y + k - 1 - i] = copy[x + i][y + j];
			}
		}
	}

2. 배열 복사 위치 잘못 선언함 -> 시간초과남
   rotate를 하기 위해선 기존 배열을 복사해둘 필요가 있다.
   다만 배열 복사 위치를 2^N 배열의 부분 배열들을 회전시킬 때마다 선언해놔서 시간 초과가 났다.
   그것도 모르고 DFS를 BFS로도 바꿔보고 온갖 난리를 다 쳐본 것 같다... ㅋㅋㅋ

3. 얼음 없어질 때 순차적으로 탐색하면서 제거하면 안 된다. 그러면 한 얼음이 없어지면서, 뒤에 얼음들도 같이 없어질 수 있기 때문이다. 그렇기에 줄어들 얼음의 좌표들을 한꺼번에 저장해둔 다음에 마지막에 한꺼번에 얼음 줄이는 작업을 진행해야 한다.

🕑 소요시간

2시간 50분

💻 풀이

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

public class Main {
	static int N, Q, M;
	static int map[][];
	static int L[];
	static boolean visited[][];
	static int iceCnt; // 덩어리가 차지하는 칸 개수

	public static void main(String[] args) throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());

		N = Integer.parseInt(st.nextToken());
		Q = Integer.parseInt(st.nextToken()); // 파이어스톰 시전 회수
		M = (int) Math.pow(2, N); // M=2^N

		map = new int[M][M];
		visited = new boolean[M][M];
		L = new int[Q];

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

		st = new StringTokenizer(br.readLine());
		for (int i = 0; i < Q; i++)
			L[i] = Integer.parseInt(st.nextToken());

		for (int i = 0; i < Q; i++) { // Q번의 파이어스톰 실행
			FireStorm(L[i]);
		}

		// 1.남아있는 얼음 양
		int sum = 0;
		for (int i = 0; i < M; i++) {
			for (int j = 0; j < M; j++) {
				sum += map[i][j];
			}
		}
		// 2. 가장 큰 덩어리가 차지하는 개수
		int res = 0;
		for (int i = 0; i < M; i++) {
			for (int j = 0; j < M; j++) {
				if (!visited[i][j] && map[i][j] != 0) {
					iceCnt = 1;
					dfs(i, j);
					res = Math.max(res, iceCnt);
				}
			}
		}
		System.out.println(sum);
		System.out.println(res);
	}

	private static void dfs(int x, int y) { // 얼음 덩어리 개수
		visited[x][y] = true;
		for (int i = 0; i < 4; i++) {
			int nx = x + dx[i];
			int ny = y + dy[i];
			if (nx < 0 || nx >= M || ny < 0 || ny >= M)
				continue;
			if (!visited[nx][ny] && map[nx][ny] > 0) {
				dfs(nx, ny);
				iceCnt++;

			}
		}
	}

	private static void FireStorm(int l) { // 파이어 스톰

		int K = (int) Math.pow(2, l); // K = 2^l

		int[][] copy = copy(map);
		for (int i = 0; i < M; i = i + K) { // KxK 크기의 격자 90도 회전
			for (int j = 0; j < M; j = j + K) {
				rotate(i, j, K, copy);
			}
		}
		decreaseIce(); // 회전 끝나면 얼음 줄이기 시작
	}

	static int dx[] = { -1, 1, 0, 0 };
	static int dy[] = { 0, 0, -1, 1 };

	private static void decreaseIce() { // 얼음 줄이기
		List<int[]> list = new ArrayList<>();

		for (int x = 0; x < M; x++) {
			for (int y = 0; y < M; y++) {
				int cnt = 0; // 얼음이 있는 칸 수
				for (int i = 0; i < 4; i++) {
					int nx = x + dx[i];
					int ny = y + dy[i];
					if (nx < 0 || nx >= M || ny < 0 || ny >= M)
						continue;
					if (map[nx][ny] > 0)
						cnt++;
				}
				if (cnt < 3) // 얼음있는 칸이 3칸 미만이면
					list.add(new int[] { x, y });
			}

		}
		for (int i = 0; i < list.size(); i++) {
			int[] cur = list.get(i);
			if (map[cur[0]][cur[1]] > 0) {
				map[cur[0]][cur[1]] -= 1;
			}
		}
	}

	private static void rotate(int x, int y, int k, int[][] copy) { // 시계방향 90도 회전

		for (int i = 0; i < k; i++) {
			for (int j = 0; j < k; j++) {
				map[x + j][y + k - 1 - i] = copy[x + i][y + j];
			}
		}
	}

	private static int[][] copy(int[][] map) {
		int data[][] = new int[M][M];
		for (int i = 0; i < M; i++) {
			for (int j = 0; j < M; j++)
				data[i][j] = map[i][j];
		}
		return data;
	}
}

🌟 비슷한 유형의 문제들
[백준 20327] 배열 돌리기6 (Gold 3)

❗ 풀어보면 좋은 문제들
[백준 17276] 배열 돌리기 (Silver 2)
[백준 16926] 배열 돌리기1 (Silver 1)
[백준 16927] 배열 돌리기2 (Gold 5)
[백준 16935] 배열 돌리기3 (Silver 1)
[백준 17406] 배열 돌리기4 (Gold 4)

참고
[백준] 20058번 - 마법사 상어와 파이어스톰 (java)
2차원 배열 회전 Rotate (Java)