[백준 / JAVA] 20058. 마법사 상어와 파이어볼 (G3)

https://www.acmicpc.net/problem/20058

 

이번 달 들어 알고리즘을 풀면서 가장 빡치는 문제다. 문제 설명을 보면 '모든 부분 격자를 시계 방향으로 90도 회전시킨다.' 라고 쓰여 있고 이렇게 예시 사진이 있다. 

 

2번은 1번에 L=1을 적용한 것이며 3번은1번에 L=2를 적용한 것이다. 1>2>3 순서되로 진행되는 것이 아니란 말이다.

 

이 사진을 보면 대부분의 사람이 1번 2번 3번 과정이 순서대로 진행됐다고 생각하지 않겠는가? 그리고 3번 테케를 틀리고 멘붕이 올 것이다. 사실 이 문제의 이동은 이런 식으로 일어난다.

 

이런 ㅆ...

 

차라리 예시 이미지가 없다면 통째로 굴러가는 걸 생각이라도 할텐데(심지어 이 편이 구현도 더 쉬움) '부분 격자'를 회전시킨 게 아니라 '부분 격자의 부분 격자'를 회전 시킨 내 잘못인건가?

 

삼성한테 받은 게 많아서 참는다...

 

내일 코테만 아니면 맥주 까는 건데

 

 

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

public class Main {
	static BufferedReader br;
	static StringTokenizer st;
	static StringBuilder sb;

	public static void main(String[] args) throws Exception {
		br = new BufferedReader(new InputStreamReader(System.in));
		st = new StringTokenizer(br.readLine());
		N = Integer.parseInt(st.nextToken());
		mapSize = (int) Math.pow(2, N);
		map = new int[mapSize][mapSize];
		int q = Integer.parseInt(st.nextToken());
		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());
		}
		st = new StringTokenizer(br.readLine());
		for (int i = 0; i < q; i++) {
			dfs(0, mapSize, 0, mapSize, Integer.parseInt(st.nextToken()));
			leakIce();
		}
		System.out.println(totalIce());
		System.out.println(biggestIce());
	}

	static int N, map[][], mapSize, maxSize = 0, dr[] = { -1, 1, 0, 0 }, dc[] = { 0, 0, -1, 1 };
	static Deque<Point> leakIceQ = new ArrayDeque<Point>();

	static int biggestIce() {
		boolean visited[][] = new boolean[mapSize][mapSize];
		Deque<Point> q = new ArrayDeque<Point>();
		for (int i = 0; i < mapSize; i++) {
			for (int j = 0; j < mapSize; j++) {
				int tmpSize = 0;
				if (map[i][j] > 0 && !visited[i][j]) {
					q.add(new Point(i, j));
					visited[i][j] = true;
					while (!q.isEmpty()) {
						Point cur = q.poll();
						tmpSize++;
						for (int d = 0; d < 4; d++) {
							int nr = cur.row + dr[d];
							int nc = cur.col + dc[d];
							if (nr < 0 || nr >= mapSize || nc < 0 || nc >= mapSize || visited[nr][nc]
									|| map[nr][nc] == 0)
								continue;
							q.add(new Point(nr, nc));
							visited[nr][nc] = true;
						}
					}
				}
				maxSize = Math.max(maxSize, tmpSize);
			}
		}
		return maxSize;
	}

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

	static void leakIce() {
		for (int i = 0; i < mapSize; i++)
			for (int j = 0; j < mapSize; j++) {
				if (map[i][j] > 0) {
					int iceCnt = 0;
					for (int d = 0; d < 4; d++) {
						int nr = i + dr[d];
						int nc = j + dc[d];
						if (nr < 0 || nr >= mapSize || nc < 0 || nc >= mapSize)
							continue;
						if (map[nr][nc] > 0)
							iceCnt++;
					}
					if (iceCnt < 3)
						leakIceQ.add(new Point(i, j));
				}
			}
		while (!leakIceQ.isEmpty()) {
			Point curIce = leakIceQ.poll();
			map[curIce.row][curIce.col]--;
		}
	}

	static void dfs(int rStart, int rEnd, int cStart, int cEnd, int grade) {
		int size = rEnd - rStart;
		if (size == Math.pow(2, grade)) {
			int tmpMap[][] = new int[size][size];
			for (int i = 0; i < size; i++) // tmpMap에 격자 복사
				tmpMap[i] = Arrays.copyOfRange(map[rStart + i], cStart, cEnd);
			for (int i = 0; i < size; i++)
				for (int j = 0; j < size; j++)
					map[rStart + j][cEnd - 1 - i] = tmpMap[i][j];
			return;
		}
		int rMid = (rStart + rEnd) / 2;
		int cMid = (cStart + cEnd) / 2;
		dfs(rStart, rMid, cStart, cMid, grade);
		dfs(rMid, rEnd, cStart, cMid, grade);
		dfs(rStart, rMid, cMid, cEnd, grade);
		dfs(rMid, rEnd, cMid, cEnd, grade);
		return;
	}

	static class Point {
		int row, col;

		public Point(int row, int col) {
			super();
			this.row = row;
			this.col = col;
		}
	}
}