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

문제

마법사 상어는 파이어볼과 토네이도를 조합해 파이어스톰을 시전할 수 있다. 오늘은 파이어스톰을 크기가 2N × 2N인 격자로 나누어진 얼음판에서 연습하려고 한다. 위치 (r, c)는 격자의 r행 c열을 의미하고, A[r][c]는 (r, c)에 있는 얼음의 양을 의미한다. A[r][c]가 0인 경우 얼음이 없는 것이다.

파이어스톰을 시전하려면 시전할 때마다 단계 L을 결정해야 한다. 파이어스톰은 먼저 격자를 2L × 2L 크기의 부분 격자로 나눈다. 그 후, 모든 부분 격자를 시계 방향으로 90도 회전시킨다. 이후 얼음이 있는 칸 3개 또는 그 이상과 인접해있지 않은 칸은 얼음의 양이 1 줄어든다. (r, c)와 인접한 칸은 (r-1, c), (r+1, c), (r, c-1), (r, c+1)이다. 아래 그림의 칸에 적힌 정수는 칸을 구분하기 위해 적은 정수이다.

마법을 시전하기 전	L = 1	L = 2

마법사 상어는 파이어스톰을 총 Q번 시전하려고 한다. 모든 파이어스톰을 시전한 후, 다음 2가지를 구해보자.

1. 남아있는 얼음 A[r][c]의 합
2. 남아있는 얼음 중 가장 큰 덩어리가 차지하는 칸의 개수

얼음이 있는 칸이 얼음이 있는 칸과 인접해 있으면, 두 칸을 연결되어 있다고 한다. 덩어리는 연결된 칸의 집합이다.

입력

첫째 줄에 N과 Q가 주어진다. 둘째 줄부터 2N개의 줄에는 격자의 각 칸에 있는 얼음의 양이 주어진다. r번째 줄에서 c번째 주어지는 정수는 A[r][c] 이다.

마지막 줄에는 마법사 상어가 시전한 단계 L1, L2, ..., LQ가 순서대로 주어진다.

출력

첫째 줄에 남아있는 얼음 A[r][c]의 합을 출력하고, 둘째 줄에 가장 큰 덩어리가 차지하는 칸의 개수를 출력한다. 단, 덩어리가 없으면 0을 출력한다.

제한

• 2 ≤ N ≤ 6
• 1 ≤ Q ≤ 1,000
• 0 ≤ A[r][c] ≤ 100
• 0 ≤ Li ≤ N

예제 입력 1 

3 1
1 2 3 4 5 6 7 8
8 7 6 5 4 3 2 1
1 2 3 4 5 6 7 8
8 7 6 5 4 3 2 1
1 2 3 4 5 6 7 8
8 7 6 5 4 3 2 1
1 2 3 4 5 6 7 8
8 7 6 5 4 3 2 1
1

예제 출력 1

284
64

예제 입력 2

3 2
1 2 3 4 5 6 7 8
8 7 6 5 4 3 2 1
1 2 3 4 5 6 7 8
8 7 6 5 4 3 2 1
1 2 3 4 5 6 7 8
8 7 6 5 4 3 2 1
1 2 3 4 5 6 7 8
8 7 6 5 4 3 2 1
1 2

예제 출력 2

280
64

예제 입력 3

3 5
1 2 3 4 5 6 7 8
8 7 6 5 4 3 2 1
1 2 3 4 5 6 7 8
8 7 6 5 4 3 2 1
1 2 3 4 5 6 7 8
8 7 6 5 4 3 2 1
1 2 3 4 5 6 7 8
8 7 6 5 4 3 2 1
1 2 0 3 2

예제 출력 3

268
64

예제 입력 4 

3 10
1 2 3 4 5 6 7 8
8 7 6 5 4 3 2 1
1 2 3 4 5 6 7 8
8 7 6 5 4 3 2 1
1 2 3 4 5 6 7 8
8 7 6 5 4 3 2 1
1 2 3 4 5 6 7 8
8 7 6 5 4 3 2 1
1 2 0 3 2 1 2 3 2 3

예제 출력 4 

248
62

예제 입력 5

3 10
1 2 3 4 5 6 7 8
8 7 6 5 4 3 2 1
1 2 3 4 5 6 7 8
8 7 6 5 4 3 2 1
1 2 3 4 5 6 7 8
8 7 6 5 4 3 2 1
1 2 3 4 5 6 7 8
8 7 6 5 4 3 2 1
1 2 3 1 2 3 1 2 3 1

예제 출력 5

246
60

예제 입력 6

3 10
1 0 3 4 5 6 7 0
8 0 6 5 4 3 2 1
1 2 0 4 5 6 7 0
8 7 6 5 4 3 2 1
1 2 3 4 0 6 7 0
8 7 0 5 4 3 2 1
1 2 3 4 5 6 7 0
0 7 0 5 4 3 2 1
1 2 3 1 2 3 1 2 3 1

예제 출력 6

37
9

 

소스코드

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

public class Main {

	private static BufferedReader br;
	private static StringTokenizer st;

	private static int N, Q, L, size, sizeL, max;
	private static int[][] map;
	private static boolean[][] visited;
	private static int[] dx = { -1, 1, 0, 0 };
	private static int[] dy = { 0, 0, -1, 1 };

	static class Ice {	// 얼음의 좌표 저장
		int r, c;

		public Ice(int r, int c) {
			super();
			this.r = r;
			this.c = c;
		}

		@Override
		public String toString() {
			return "Ice [r=" + r + ", c=" + c + "]";
		}

	}

	public static void main(String[] args) throws IOException {
		br = new BufferedReader(new InputStreamReader(System.in));
		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 r = 0; r < size; r++) {
			st = new StringTokenizer(br.readLine());
			for (int c = 0; c < size; c++) {
				map[r][c] = Integer.parseInt(st.nextToken());
			}
		}

		st = new StringTokenizer(br.readLine());
		for (int i = 0; i < Q; i++) {
			L = Integer.parseInt(st.nextToken());	// 단계
			sizeL = (int) Math.pow(2, L);	// 부분 격자의 크기
			for (int r = 0; r < size; r += sizeL) { // 시계 방향으로 90도 회전
				for (int c = 0; c < size; c += sizeL) {
					rotate(r, c, sizeL);
				}
			}

			melt(); // 얼음 양 조정
		}

		int remain = count(); // 남은 얼음 양

		visited = new boolean[size][size];
		for (int r = 0; r < size; r++) { // 큰 덩어리 칸 개수
			for (int c = 0; c < size; c++) {
				if (map[r][c] > 0 && !visited[r][c]) {
					int tmp = bfs(r, c);
					max = Math.max(max, tmp);
				}
			}
		}

		System.out.println(remain);
		System.out.println(max);
	}

	private static int bfs(int r, int c) {	// bfs 탐색을 통해 인접한 얼음이 몇 개 있는지 확인
		Queue<Ice> queue = new LinkedList<>();
		queue.add(new Ice(r, c));

		visited[r][c] = true;

		int cnt = 1;
		while (!queue.isEmpty()) {
			Ice q = queue.poll();

			for (int d = 0; d < 4; d++) {
				int nx = q.r + dx[d];
				int ny = q.c + dy[d];

				if (isIn(nx, ny) && !visited[nx][ny] && map[nx][ny] > 0) {
					cnt++;
					visited[nx][ny] = true;
					queue.add(new Ice(nx, ny));
				}
			}
		}

		return cnt;
	}

	private static int count() {	// 얼음의 양을 계산
		int cnt = 0;
		for (int r = 0; r < size; r++) {
			for (int c = 0; c < size; c++) {
				if (map[r][c] > 0)
					cnt+=map[r][c];
			}
		}

		return cnt;
	}

	private static void melt() {	// 인접한 얼음의 칸이 3개 미만이면 얼음 양 1 감소시킴
		Queue<Ice> queue=new LinkedList<>();
		for (int r = 0; r < size; r++) {
			for (int c = 0; c < size; c++) {
				if (map[r][c] == 0)
					continue;
				int cnt = 0;
				for (int d = 0; d < 4; d++) {
					int nx = r + dx[d];
					int ny = c + dy[d];

					if (isIn(nx, ny) && map[nx][ny] > 0)
						cnt++;
				}
				if (cnt < 3)
					queue.add(new Ice(r, c));
			}
		}
		
		while(!queue.isEmpty()) {
			Ice q=queue.poll();
			
			map[q.r][q.c]--;
		}
	}

	private static void rotate(int R, int C, int s) {	// 시계 방향으로 90도 회전함
		int[][] tmp = new int[size][size];
		for (int r = R; r < R + s; r++) {
			for (int c = C; c < C + s; c++) {
				tmp[c + R - C][R + C + s - r - 1] = map[r][c];
			}
		}

		for (int r = R; r < R + s; r++) {
			for (int c = C; c < C + s; c++) {
				map[r][c] = tmp[r][c];
			}
		}
	}

	private static boolean isIn(int r, int c) {
		return r >= 0 && r < size && c >= 0 && c < size;
	}
}

1. 시계 방향 90도 회전

시작점=(x, y), 부분 격자의 크기=s 일 때

(x, y) (x, y+1) ...... (x, y+s-1) -> (x, y+s-1) (x+1, y+s-1) ...... (x+s-1, y+s-1)

(x+1, y) (x+1, y+1) ...... (x+1, y+s-1) -> (x, y+s-2) (x+1, y+s-2) ...... (x+s-1, y+s-2) 

......

(x+s-1, y) (x+s-1, y+1) ...... (x+s-1, y+s-1) -> (x, y) (x+1, y) ...... (x+s-1, y)

 

즉, newMap[c-y+x][x+y+s-r-1]=map[r][c]로 이동한다는 것을 알 수 있습니다.

 

2. 인접한 얼음 칸이 3개 미만인 경우 얼음 양을 1 감소시킴

2중 for문을 돌며 인접한 얼음의 칸 수를 계산하여 3개 미만인 경우를 전부 큐에 넣어줍니다. 2중 for문을 모두 돌고 난 후, 큐에 있는 값을 하나씩 빼면서 해당 얼음의 양을 1만큼 감소시킵니다. 

 

3. 위 과정을 Q번 반복하고 남은 얼음의 합과 인접한 얼음의 개수가 가장 많은 경우를 구해줍니다.