[java] 백준(BOJ) - 마법사 상어와 파이어스톰

문제

백준-마법사 상어와 파이어스톰
파이어스톰이 명령에 따라 Q번 시전 한 후 남아있는 얼음의 합과 얼음 중 가장 큰 덩어리가 차지하는 칸의 갯수를 구하는 문제

• 제한 사항
  맵의 크기 2^N : 2 ≤ N ≤ 6
  마법 시전 횟수 Q : 1 ≤ Q ≤ 1,000
  각 얼음의 양 A[r][c] : 0 ≤ A[r][c] ≤ 100
  시전 단계 L : 0 ≤ Li ≤ N

풀이

맵의 크기는 N*N이 아닌 2^N * 2^N임을 유의해야한다
2의 N승으로 크기를 구해서 map이라는 int 배열을 선언한다

그 후 2^L * 2^L크기로 나눠서 회전을 해야한다
단계의 범위를 보면, 0 이상 N 이하이다
2^L 크기로 나눠서 회전해야하므로 0이거나 N인경우에는 회전하지 않는다
(💥얼음이 녹는과정은 진행해야함💥)

분할

divide conquer느낌으로 4분할을 했다
split(시작x, 끝x, 시작y, 끝y, 가로길이)메서드를 구현했다

먼저 맵의 크기를 size라고 한다면
초기 함수 값은 split(0, size, 0, size, 2^L)이다
(끝x과 끝y는 포함하지 않는다)

대략적으로 설명하자면 split 함수의 로직은 아래와 같다

• split함수(시작x, 끝x, 시작y, 끝y, 가로길이)
  1. 인자 ‘가로길이’와 [끝x - 시작x]를 비교한다
  2. 두 값이 같다면 현재 범위가 회전할 범위이므로 90도 회전한다
     2-1. 두 값이 다르다면, 현재 범위를 4분할해서 split을 호출한다
  • 예시 L = 2인 경우, 4 * 4크기로 나눠서 회전을 해야한다
    map의 크기가 8 * 8 이라면 초기 호출은 split(0, 8, 0, 8, 4)가 된다
    • split(0, 8, 0, 8, 4)
      split함수 내부에서 4와 (8-0)을 비교한다
      두 값이 다르므로 4분할한 split 을 호출한다

      split(0, 4, 0, 4, 4) // 좌상단
      split(0, 4, 4, 8, 4) // 우상단
      split(4, 8, 0, 4, 4) // 좌하단
      split(4, 8, 4, 8, 4) // 우하단

      • split(0, 4, 0, 4, 4)
        4와 (4-0)을 비교한다
        두 값이 같으므로 90도 회전한다

회전

90도 회전하는 부분은 가장 안쪽부터 회전하게 했다

int mid = (ex - sx) / 2; // 현재 분할에서 한 구역의 크기
// 가장 안쪽의 좌상단 위치
int mx = sx + mid - 1; 
int my = sy + mid - 1;
for (int i = 1; i <= s / 2; i++) {  // s : 가로 폭
	turn90(mx, my, i * 2); 
	mx--;
	my--;
}

[0, 0]에서 [3, 3]까지의 분할구역을 회전해야 할 때,
가장 안쪽(노란색 점)을 회전한 후
바깥쪽(초록색 점)으로 이동한다

바깥쪽으로 갈때(노란점->초록점) (-1,-1)씩 움직인다

90도 회전은 map[mx][my]부터 map[mx][my + i*2]까지(가장 윗줄,[25,17,9,1]) tmp에 복사한 다음,
왼쪽 세로를 상단으로, 하단을 왼쪽 세로로 … 이런식으로 복사했다
(코드참조)

얼음 녹이기

회전을 마친 후, 각 얼음은 인접 방향 3개 이상 얼음이 존재하지 않으면 1씩 감소한다(녹는다)
이때, 배열을 순회하면서 감소시키면 안된다
현재 칸이 1이고 녹아야해서 0으로 만들면, 다음칸에 영향을 미칠 수 있기 떄문이다

시행착오

얼추 코드를 작성한 후 테케3의 답이 맞지않았다
디버깅하면서 회전값도 확인했는데, 원인은 다른 곳에 있었다
L이 0이거나 N이면 continue로 써서 얼음이 녹는단계를 진행하지 않았기 때문이었다
회전만 안할뿐이지 녹아야 할 얼음은 녹는다..

소스코드

코드도 분할 ~~!

맵 분할 및 회전

private static void split(int sx, int ex, int sy, int ey, int s) {
	int mid = (ex - sx) / 2;
	if (ex - sx == s) {
	// 90도 돌리기
		int mx = sx + mid - 1;
		int my = sy + mid - 1;
		for (int i = 1; i <= s / 2; i++) {
			turn90(mx, my, i * 2);
			mx--;
			my--;
		}
	} else {
		split(sx, sx + mid, sy, sy + mid, s);
		split(sx, sx + mid, sy + mid, ey, s);
		split(sx + mid, ex, sy, sy + mid, s);
		split(sx + mid, ex, sy + mid, ey, s);
	}
}

private static void turn90(int sx, int sy, int width) {
	int tmp[] = new int[width];
	// 가장 상단 복사
	for (int i = 0; i < width; i++) {
		tmp[i] = map[sx][sy + i];
	}
	// 왼쪽 세로를 상단으로 복사
	for (int i = 1; i < width; i++) {
		map[sx][sy + width - i - 1] = map[sx + i][sy];
	}
	// 하단을 왼쪽 세로로 복사
	for (int i = 1; i < width; i++) {
		map[sx + i][sy] = map[sx + width - 1][sy + i];
	}
	// 오른쪽 세로를 하단으로 복사
	for (int i = 1; i < width; i++) {
		map[sx + width - 1][sy + i] = map[sx + width - i - 1][sy + width - 1];
	}
	for (int i = 0; i < width - 1; i++) {
		map[sx + i][sy + width - 1] = tmp[i];
	}
}

얼음 녹는 부분

//	 얼음 녹는 부분
private static void melt() {
	q.clear();
	for (int i = 0; i < size; i++) {
		for (int j = 0; j < size; j++) {
			if (map[i][j] > 0) {
				int cnt = 0;
				for (int k = 0; k < 4; k++) {
					int nx = i + dx[k];
					int ny = j + dy[k];
					if (nx > -1 && ny > -1 && nx < size && ny < size && map[nx][ny] > 0) {
						cnt++;
					}
				}
				if (cnt < 3)
					q.add(new Point(i, j));
			}
		}
	}
	while (!q.isEmpty()) {
		Point curr = q.poll();
		map[curr.x][curr.y]--;
	}
}

나머지

import java.awt.Point;
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 b20058_마법사상어와파이어스톰 {

	private static int Q;
	private static int N;
	private static int[][] map;
	private static int[] order;
	static int dx[] = { 0, 0, 1, -1 };
	static int dy[] = { 1, -1, 0, 0 };
	static int size;
	static Queue<Point> q = new LinkedList<>();

	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());
		size = 1;

		for (int i = 0; i < N; i++) {
			size *= 2;
		}
		map = new int[size][size];
		order = new int[Q];
		for (int i = 0; i < size; i++) {
			st = new StringTokenizer(br.readLine());
			for (int j = 0; j < size; j++) {
				map[i][j] = Integer.parseInt(st.nextToken());
			}
		}

		st = new StringTokenizer(br.readLine());
		for (int i = 0; i < Q; i++) {
			order[i] = Integer.parseInt(st.nextToken());
		}
		for (int i = 0; i < Q; i++) {
			int L = order[i];
			if (L == 0 || L == N) {
				melt();
				continue;
			}
			int cell = 1;
			for (int j = 0; j < L; j++) {
				cell *= 2;
			}
			// 회전
			split(0, size, 0, size, cell);
			// 얼음 녹기
			melt();
		}
		// 마지막 얼음 양 총합과 큰 덩어리 얼음갯수 구하는 부분(bfs 사용)
		long ans = 0;
		int max = 0;
		boolean chk[][] = new boolean[size][size];
		q.clear();
		for (int i = 0; i < size; i++) {
			for (int j = 0; j < size; j++) {
				if (map[i][j] > 0 && !chk[i][j]) {
					int cnt = 1;
					q.add(new Point(i, j));
					chk[i][j] = true;

					while (!q.isEmpty()) {
						Point curr = q.poll();
						ans += map[curr.x][curr.y];
						for (int k = 0; k < 4; k++) {
							int nx = curr.x + dx[k];
							int ny = curr.y + dy[k];
							if (nx > -1 && ny > -1 && nx < size && ny < size && !chk[nx][ny] && map[nx][ny] > 0) {
								q.add(new Point(nx, ny));
								chk[nx][ny] = true;
								cnt++;
							}
						}
					}
					max = Math.max(max, cnt);
				}
			}
		}
		// end
		System.out.println(ans);
		System.out.println(max);
	}
}