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

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

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

[ 문제풀이 ]

2차원 배열을 회전하는 법을 알고 있다면 시리즈 3개의 문제 중 가장 쉽게 풀 수 있지 않을까 싶다.

​1. A(i, j)의 값을 시계방향으로 90도 회전하려면 A(j, N-i-1)로 하면 된다. 이 문제는 배열 전체를 회전하는 것이 아닌 나눠진 격자의 배열을 각각 따로 회전시키는 것이기 때문에 이 부분만 조심해서 구현하면 된다.

이 문제에서 가장 어렵다고 생각하는 부분이 여기라 생각해서 이 부분을 해결했다면 나머지 시뮬레이션 및 탐색 부분은 쉽게 구현할 수 있을 것이다.

​2. 매번 느끼지만 문제를 똑바로 읽자!!! 나는 남아있는 얼음 중 가장 큰 덩어리가 차지하는 칸의 개수라는 문장에서 덩어리가 얼음을 뜻하는 것으로 이해해서 가장 큰 얼음을 포함하는 칸의 개수를 구하는 것이라고 이해하고 구하였다.

하지만, 덩어리는 얼음이 연결된 칸의 집합을 의미하기 때문에 모든 얼음의 집합을 구해서 최댓값을 찾아야 한다.

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.StringTokenizer;

public class Main {
	static int N, Q, mapSize, answer;
	static int[] L;
	static int[][] A, temp;
	static boolean[][] visit;
	static int[][] dir = {{0, -1}, {1, 0}, {0, 1}, {-1, 0}};

	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());
		N = Integer.parseInt(st.nextToken());
		Q = Integer.parseInt(st.nextToken());
		mapSize = 1 << N;
		A = new int[mapSize][mapSize];
		temp = new int[mapSize][mapSize];
		visit = new boolean[mapSize][mapSize];

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

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

		int t = 0;
		while (t < Q) {
			//2^L x 2^L 크기의 부분 격자로 나눈 후 시계방향 90도 회전
			if (L[t] != 0) {
				int len = 1 << L[t];
				for (int i = 0; i < mapSize; i += len) {
					for (int j = 0; j < mapSize; j += len) {
						rotation(i, j, len);
					}
				}
			}
			
			//얼음이 있는 칸 3개 또는 그 이상과 인접해있지 않은 칸은 얼음의 양을 1줄임
			for (int i = 0; i < mapSize; ++i) {
				for (int j = 0; j < mapSize; ++j) {
					if (!isVaild(i, j)) {
						visit[i][j] = true;
					}
				}
			}

			for (int i = 0; i < mapSize; ++i) {
				for (int j = 0; j < mapSize; ++j) {
					if (visit[i][j]) {
						A[i][j]--;
					}
				}
			}
			
			for (int i = 0; i < mapSize; ++i) {
				Arrays.fill(visit[i], false);
			}
			t++;
		}
		System.out.println(getIceSum());
		System.out.println(getLargePiece());
	}

	public static void rotation(int sy, int sx, int len) {
		for (int i = 0; i <  len; ++i) {
			for (int j = 0; j < len; ++j) {
				temp[j][len - i - 1] = A[i + sy][j + sx];
			}
		}

		for (int i = 0; i <  len; ++i) {
			for (int j = 0; j < len; ++j) {
				A[i + sy][j + sx] = temp[i][j];
			}
		}
	}

	public static boolean isVaild(int y, int x) {
		int cnt = 0;
		
		for (int d = 0; d < 4; ++d) {
			int ny = y + dir[d][0];
			int nx = x + dir[d][1];
			
			if (ny < 0 || nx < 0 || ny >= mapSize || nx >= mapSize) continue;
			if (A[ny][nx] <= 0) continue;
			
			cnt++;
		}
	
		return cnt < 3 ? false : true;
	}

	public static int getIceSum() {
		int sum = 0;
		
		for (int i = 0; i < mapSize; ++i) {
			for (int j = 0; j < mapSize; ++j) {
				if (A[i][j] > 0) {
					sum += A[i][j];
				}
			}
		}
		
		return sum;
	}
	
	public static int getLargePiece() {
		int maxLargePiece = 0;
		
		for (int i = 0; i < mapSize; ++i) {
			for (int j = 0; j < mapSize; ++j) {
				if (visit[i][j] || A[i][j] <= 0) continue;
				dfs(i, j);
				maxLargePiece = Math.max(maxLargePiece, answer);
				answer = 0;
			}
		}
		
		return maxLargePiece;
	}
	
	public static void dfs(int y, int x) {
		visit[y][x] = true;
		answer++;
		
		for (int d = 0; d < 4; ++d) {
			int ny = y + dir[d][0];
			int nx = x + dir[d][1];

			if (ny < 0 || nx < 0 || ny >= mapSize || nx >= mapSize) continue;
			if (visit[ny][nx] || A[ny][nx] <= 0) continue;

			dfs(ny, nx);
		}
	}
}