문제
마법사 상어는 파이어볼과 토네이도를 조합해 파이어스톰을 시전할 수 있다. 오늘은 파이어스톰을 크기가 2^N × 2^N인 격자로 나누어진 얼음판에서 연습하려고 한다. 위치 (r, c)는 격자의 r행 c열을 의미하고, A[r][c]는 (r, c)에 있는 얼음의 양을 의미한다. A[r][c]가 0인 경우 얼음이 없는 것이다.
파이어스톰을 시전하려면 시전할 때마다 단계 L을 결정해야 한다. 파이어스톰은 먼저 격자를 2^L × 2^L 크기의 부분 격자로 나눈다. 그 후, 모든 부분 격자를 시계 방향으로 90도 회전시킨다. 이후 얼음이 있는 칸 3개 또는 그 이상과 인접해있지 않은 칸은 얼음의 양이 1 줄어든다. (r, c)와 인접한 칸은 (r-1, c), (r+1, c), (r, c-1), (r, c+1)이다. 아래 그림의 칸에 적힌 정수는 칸을 구분하기 위해 적은 정수이다.
마법사 상어는 파이어스톰을 총 Q번 시전하려고 한다. 모든 파이어스톰을 시전한 후, 다음 2가지를 구해보자.
- 남아있는 얼음 A[r][c]의 합
- 남아있는 얼음 중 가장 큰 덩어리가 차지하는 칸의 개수
얼음이 있는 칸이 얼음이 있는 칸과 인접해 있으면, 두 칸을 연결되어 있다고 한다. 덩어리는 연결된 칸의 집합이다.
첫째 줄에 N과 Q가 주어진다. 둘째 줄부터 2N개의 줄에는 격자의 각 칸에 있는 얼음의 양이 주어진다. r번째 줄에서 c번째 주어지는 정수는 A[r][c] 이다.
마지막 줄에는 마법사 상어가 시전한 단계 L1, L2, ..., LQ가 순서대로 주어진다.
첫째 줄에 남아있는 얼음 A[r][c]의 합을 출력하고, 둘째 줄에 가장 큰 덩어리가 차지하는 칸의 개수를 출력한다. 단, 덩어리가 없으면 0을 출력한다.
[풀이 코드]
import java.io.*;
import java.util.*;
public class Main {
static int N, Q, n, l, count;
static int[][] arr;
static boolean[][] v;
static int[] dr = {0, 0, 1, -1};
static int[] dc = {1, -1, 0, 0};
public static void main(String[] args) throws Exception {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st = new StringTokenizer(br.readLine());
N = Integer.parseInt(st.nextToken());
Q = Integer.parseInt(st.nextToken());
n = (int) Math.pow(2, N);
arr = new int[n][n];
for (int i = 0; i < n; i++) {
st = new StringTokenizer(br.readLine());
for (int j = 0; j < n; j++) {
arr[i][j] = Integer.parseInt(st.nextToken());
}
}
st = new StringTokenizer(br.readLine());
for (int q = 0; q < Q; q++) {
int L = Integer.parseInt(st.nextToken());
l = (int) Math.pow(2, L);
// 배열 회전
for (int i = 0; i < n; i+=l) {
for (int j = 0; j < n; j+=l) {
rotate(i, j);
}
}
// 상하좌우 확인
v = new boolean[n][n];
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
if(arr[i][j] > 0) {
check(i, j, v);
}
}
}
// 확인된 얼음칸 1 삭제
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
if(v[i][j]) {
arr[i][j]--;
}
}
}
}
// 남아있는 얼음의 합
System.out.println(ice_sum());
// 가장 큰 덩어리가 차지하는 칸의 개수
count = Integer.MIN_VALUE;
v = new boolean[n][n];
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
if(arr[i][j]>0 && !v[i][j]) {
big_count(i, j);
}
}
}
if(count==Integer.MIN_VALUE) {
System.out.println(0);
}else {
System.out.println(count);
}
}
private static void rotate(int r, int c) {
int[][] temp = new int[l][l];
for (int i = 0; i < l; i++) {
for (int j = 0; j < l; j++) {
temp[j][l-1-i] = arr[r+i][c+j];
}
}
for (int i = 0; i < l; i++) {
for (int j = 0; j < l; j++) {
arr[r+i][c+j] = temp[i][j];
}
}
}
private static void check(int r, int c, boolean[][] v) {
int sum = 0;
for (int d = 0; d < 4; d++) {
int nr = r + dr[d];
int nc = c + dc[d];
if(nr>=0 && nr<n && nc>=0 && nc<n && arr[nr][nc]>0) sum++;
}
if(sum<3) v[r][c] = true;
}
private static int ice_sum() {
int sum = 0;
for(int[] a : arr) {
for(int b : a) {
if(b > 0) sum+=b;
}
}
return sum;
}
static class Point {
int r, c;
Point(int r, int c) {
this.r=r;
this.c=c;
}
}
private static void big_count(int r, int c) {
Queue<Point> queue = new ArrayDeque<>();
queue.offer(new Point(r, c));
v[r][c] = true;
int cnt = 0;
while(!queue.isEmpty()) {
Point p = queue.poll();
cnt++;
for (int d = 0; d < 4; d++) {
int nr = p.r + dr[d];
int nc = p.c + dc[d];
if(nr>=0 && nr<n && nc>=0 && nc<n && arr[nr][nc]>0 && !v[nr][nc]) {
queue.offer(new Point(nr, nc));
v[nr][nc] = true;
}
}
}
count = Math.max(count, cnt);
}
}이 문제를 읽었을 때, 헷갈리는 문장이 되게 많았다.
첫 번째로
이후 얼음이 있는 칸 3개 또는 그 이상과 인접해있지 않은 칸은 얼음의 양이 1 줄어든다.
각 칸에서 상하좌우 인접한 칸들 중 얼음이 있는 칸의 개수가 3 미만이면, 그 칸의 얼음을 1 줄인다. 와 같이 썻으면 바로 이해가 됐을텐데.. 저 문장은 이해가 잘 되지 않았다. 내가 문해력이 많이 부족한가보다 ㅠㅠ
두 번째로
남아있는 얼음 중 가장 큰 덩어리가 차지하는 칸의 개수
처음에 이 말 뜻은 남아있는 얼음 중 가장 큰 얼음의 개수를 구하는 건 줄 알았다. 그래서 해당 로직을 구현했고, 예제에 있는 입력을 넣으니 값이 다르게 나와 곰곰히 생각을 해봤고, BFS를 돌려서 최대로 많은 칸의 개수를 출력하면 됐다.
얼음이 없다면 0을 출력해야되는데 count의 초기값이 Integer.MIN_VALUE 이기 때문에 오답이 나왔었다. 그래서 if문을 사용해 해결했다.
이 문제는 배열 돌리기와 BFS가 중요한 문제다.
