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

Problem

---

Solve

풀이 순서는 아래와 같다.

1. 2^N * 2^N 크기의 격자인 map을 2^L * 2^L 크기의 격자로 나눈다.
2. 나눈 격자 안에서 각 얼음을 90도 회전하여 위치를 갱신한다.
3. 그 후 map의 얼음 중 인접해 있는 얼음이 3개 미만이라면 해당 얼음의 양을 -1로 감소한다.
4. 이를 Q번 반복한다.
5. 반복 후 남아있는 얼음 합과 가장 큰 덩어리가 차지하는 칸의 개수를 'BFS'를 통해 구한다.

2^L * 2^L 크기의 격자로 나누어 줄때는 2^L 크기 만큼 기준 좌표(나누어줄 격자의 왼쪽 위)를 이동시켜주고 나누어준 격자의 범위안에서 위치를 변경시켜준다.

static void moveIce(int l) {
		int rangSize = (int)Math.pow(2, l);
		int[][] cloneMap = new int[mapSize][mapSize];

		//r : 기준 좌표의 y축, c : 기준 좌표의 x축
		for (int r = 0; r < mapSize; r += rangSize) {
			for (int c = 0; c < mapSize; c += rangSize) {
            	//i : 나눠줄 격자의 y축, j : 나눠줄 격자의 x축
				for(int i = 0;i<rangSize;i++){
					for(int j = 0;j<rangSize;j++){
						cloneMap[r+j][c+rangSize-i-1] = map[r+i][c+j];
					}
				}
			}
		}

		map = cloneMap;
	}

---

Code

public class 마법사상어와파이어스톰 {
	static int N;
	static int Q;
	static int[] L;
	static int[][] map;
	static int mapSize;
	static int[] dy = {-1, 0, 1, 0};
	static int[] dx = {0, -1, 0, 1};

	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());
		mapSize = (int)Math.pow(2, N);

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

		//각 마법때의 2^L의 값
		L = new int[Q];
		st = new StringTokenizer(br.readLine(), " ");
		for (int i = 0; i < Q; i++) {
			L[i] = Integer.parseInt(st.nextToken());
		}

		StringBuilder sb = new StringBuilder();
        //Q번의 마법
		for (int i = 0; i < Q; i++) {
			start(i);
		}
        //Q번 반복 후 남아있는 얼음의 합과 큰 덩어리의 칸 개수 구하기
		checkIceGroup(sb);

		bw.write(sb.toString());
		bw.flush();
		bw.close();
	}

	static void checkIceGroup(StringBuilder sb) {
		boolean[][] visit = new boolean[mapSize][mapSize];
        //총 얼음 개수
		int iceCount = 0;
        //가장 큰 덩어리의 얼음칸 개수
		int iceGroupRange = 0;
		for (int i = 0; i < mapSize; i++) {
			for (int j = 0; j < mapSize; j++) {
				iceCount += map[i][j];
				if (map[i][j] != 0 && !visit[i][j]){
                	//가장 큰 얼음 개수 갱신
					iceGroupRange = Math.max(iceGroupRange, bfs(i, j, visit));
				}
			}
		}

		sb.append(iceCount);
		sb.append('\n');
		sb.append(iceGroupRange);
	}

	static int bfs(int y, int x, boolean[][] visit) {
		Queue<int[]> queue = new LinkedList<>();

		queue.offer(new int[] {y, x});
		visit[y][x] = true;

		int groupSize = 1;
		while (!queue.isEmpty()) {
			int[] current = queue.poll();
			for (int i = 0; i < 4; i++) {
				int ny = current[0] + dy[i];
				int nx = current[1] + dx[i];
				if (ny >= 0 && nx >= 0 && ny < mapSize && nx < mapSize && !visit[ny][nx] && map[ny][nx] > 0) {
					queue.offer(new int[] {ny, nx});
					visit[ny][nx] = true;
					groupSize++;
				}
			}
		}

		return groupSize;
	}

	static void start(int turn) {
		int l = L[turn];

		//얼음 이동
		moveIce(l);

		//인접 3개 미만의 얼음 양 감소
		removeIce();
	}

	static void removeIce() {
		int[][] cloneMap = mapClone();
		int adjacentIce = 0;
		for (int i = 0; i < mapSize; i++) {
			for (int j = 0; j < mapSize; j++) {
				adjacentIce = 0;
				if (map[i][j] == 0)
					continue;

				for (int d = 0; d < 4; d++) {
					int ny = i + dy[d];
					int nx = j + dx[d];
					if (ny >= 0 && nx >= 0 && nx < mapSize && ny < mapSize && map[ny][nx] > 0) {
						adjacentIce++;
					}
				}

				//인접한 얼음 칸이 3개 미만이라면 얼음 양 감소
				if (adjacentIce < 3) {
					cloneMap[i][j]--;
				}
			}
		}

		map = cloneMap;
	}

	static void moveIce(int l) {
		int rangSize = (int)Math.pow(2, l);
		int[][] cloneMap = new int[mapSize][mapSize];

		//r : 기준 좌표의 y축, c : 기준 좌표의 x축
		for (int r = 0; r < mapSize; r += rangSize) {
			for (int c = 0; c < mapSize; c += rangSize) {
            	//i : 나눠줄 격자의 y축, j : 나눠줄 격자의 x축
				for(int i = 0;i<rangSize;i++){
					for(int j = 0;j<rangSize;j++){
						cloneMap[r+j][c+rangSize-i-1] = map[r+i][c+j];
					}
				}
			}
		}

		map = cloneMap;
	}

	static int[][] mapClone() {
		int[][] cloneMap = new int[mapSize][mapSize];

		for (int i = 0; i < mapSize; i++) {
			for (int j = 0; j < mapSize; j++) {
				cloneMap[i][j] = map[i][j];
			}
		}
		return cloneMap;
	}
}

---

Result

2^L * 2^L 크기의 격자로 나누었을때 90도 회전을 잘못 이해해서 오래걸림..

---

Reference