[Boj_20058] 마법사 상어와 파이어스톰

📎 문제 링크

https://www.acmicpc.net/problem/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)이다. 아래 그림의 칸에 적힌 정수는 칸을 구분하기 위해 적은 정수이다.

마법사 상어는 파이어스톰을 총 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

 

📍 문제 정보

• 🥇  문제 레벨 : 골드 3
• 🔔  문제 유형 : 구현, 그래프 이론, 그래프 탐색, 시뮬레이션, 너비 우선 탐색, 깊이 우선 탐색
• 💬  풀이 언어 : JAVA

 

🤔 문제 풀이

파이어스톰의 시전 단계는 아래와 같다.

1. 격자를 2L × 2L 크기의 부분 격자로 나눈다.
   • 시전할 때마다 단계 L을 결정한다.
2. 모든 부분 격자를 시계 방향으로 90도 회전시킨다.
3. 얼음이 있는 칸 3개 또는 그 이상과 인접해있지 않은 칸은 얼음의 양이 1 줄어든다.
4. 위 과정을 Q 만큼 반복한다.

 

먼저, 부분 격자를 시계 방향으로 90도 회전시키기 위해 예시를 들어보자.

아래와 같은 3 x 3 크기의 부분 격자가 있다고 해보자.

(0, 0)	(0, 1)	(0, 2)
(1, 0)	(1, 1)	(1, 2)
(2, 0)	(2, 1)	(2, 2)

                                   [ map ]

격자를 시계 방향으로 90도 회전시키면 다음과 같다.

(2, 0)	(1, 0)	(0, 0)
(2, 1)	(1, 1)	(0, 1)
(2, 2)	(1, 2)	(0, 2)

                                  [ result ]

 

결과적으로 아래와 같은 공식을 찾을 수 있다.

result[i][j] = map[n-1-j][i]

 

위 규칙을 응용해서 코드를 작성해 보면 아래와 같다.

private static int[][] divide(int l) {
    int[][] tmp = new int[n][n];
    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, l, tmp);
        }
    }

    return tmp;
}

private static void rotate(int x, int y, int l, int[][] tmp) {
    for (int i = 0; i < l; i++) {
        for (int j = 0; j < l; j++) {
            tmp[i+x][j+y] = map[x+l-1-j][y+i];
        }
    }
}

 

부분 격자 90도 회전을 완료했다면,

이제 모든 얼음 칸 주위를 탐색하며 인접 얼음 칸이 3개 미만인 칸을 찾아 얼음을 1 녹여줘야 한다.

 

이때, 주의할 점은 map 배열을 직접적으로 변경하면 얼음이 줄어든 뒤 상태가 다른 칸에 영향을 줄 수 있다.

그러므로 tmp 배열을 생성해 map의 상태를 복사하여 얼음을 녹인 결과만 따로 저장해두었다.

private static int[][] melt() {
    int[][] tmp = new int[n][n];
    for (int i = 0; i < n; i++) {
        tmp[i] = Arrays.copyOf(map[i], n); // n은 복사 할 길이
    }

    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            if (map[i][j] == 0) continue;
            
            int cnt = 0; // 인접한 얼음이 있는 칸의 개수
            for (int d = 0; d < 4; d++) {
                int nx = i + dx[d];
                int ny = j + dy[d];

                if (nx >= 0 && nx < n && ny >= 0 && ny < n) {
                    if (map[nx][ny] > 0) cnt++;
                }
            }

            if (cnt < 3) tmp[i][j]--; // 3개 미만이라면 얼음 녹이기
        }
    }

    return tmp;
}

 

위 과정을 Q 만큼 반복한 뒤, 남아있는 얼음의 합과 가장 큰 덩어리가 차지하는 칸의 개수를 구한다.

너비 우선 탐색(BFS)를 사용해 가장 큰 덩어리의 칸 개수를 구하면서 남아있는 얼음의 합도 같이 구해줬다.

private static void biggest() {
    Queue<int[]> que = new LinkedList<>();
    boolean[][] checked = new boolean[n][n];

    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            total += map[i][j]; // 남아있는 얼음의 합
            
            if (map[i][j] > 0 && !checked[i][j]) {
                que.offer(new int[]{i, j});
                checked[i][j] = true;
                
                int cnt = 1; // 현재 영역의 칸의 개수
                 while (!que.isEmpty()) {
                    int[] now = que.poll();

                    for (int d = 0; d < 4; d++) {
                        int nx = now[0] + dx[d];
                        int ny = now[1] + dy[d];

                        if (nx >= 0 && nx < n && ny >= 0 && ny < n) {
                            if (map[nx][ny] > 0 && !checked[nx][ny]) {
                                que.offer(new int[]{nx, ny});
                                checked[nx][ny] = true;
                                cnt++;
                            }
                        }
                    }
                }
                
                max = Math.max(max, cnt);
            }
        }
    }
}

 

위 풀이의 코드를 바탕으로 전체적인 코드를 작성해 보면 아래와 같다.

 

✔ 코드

메모리 : 64392KB
시간 : 248ms

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

public class Main {
    static int n, q;
    static int[][] map;
    static int[] dx = {-1, 1, 0, 0};
    static int[] dy = {0, 0, -1, 1};
    static int total, max;
    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()); // 파이어스톰을 총 Q번 시전

        n = (int) Math.pow(2, n);
        map = new int[n][n]; // 2N × 2N인 격자
        for (int i = 0; i < n; i++) {
            st = new StringTokenizer(br.readLine());
            for (int j = 0; j < n; j++) {
                map[i][j] = Integer.parseInt(st.nextToken());
            }
        }

        int[] l = new int[q]; // 마법사 상어가 시전한 단계
        st = new StringTokenizer(br.readLine());
        for (int i = 0; i < q; i++) {
            l[i] = Integer.parseInt(st.nextToken());
        }

        for (int i = 0; i < q; i++) {
            map = divide(l[i]); // 부분 격자 나누기
            map = melt(); // 인접한 얼음 칸이 3개 미만인 칸 찾아 얼음 녹이기
        }

        // 남아있는 얼음의 합, 가장 큰 덩어리가 차지하는 칸의 개수
        total = max = 0;
        biggest();

        StringBuilder sb = new StringBuilder();
        sb.append(total).append("\n").append(max);

        System.out.println(sb.toString());

        br.close();
    }

    private static int[][] divide(int l) {
        int[][] tmp = new int[n][n];
        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, l, tmp); // 시계 방향으로 90도 회전
            }
        }

        return tmp;
    }

    private static void rotate(int x, int y, int l, int[][] tmp) {
        for (int i = 0; i < l; i++) {
            for (int j = 0; j < l; j++) {
                tmp[i+x][j+y] = map[x+l-1-j][y+i];
            }
        }
    }
    
    private static int[][] melt() {
        int[][] tmp = new int[n][n];
        for (int i = 0; i < n; i++) {
            tmp[i] = Arrays.copyOf(map[i], n);
        }

        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                if (map[i][j] == 0) continue;
            
                int cnt = 0; // 인접한 얼음이 있는 칸의 개수
                for (int d = 0; d < 4; d++) {
                    int nx = i + dx[d];
                    int ny = j + dy[d];

                    if (nx >= 0 && nx < n && ny >= 0 && ny < n) {
                        if (map[nx][ny] > 0) cnt++;
                    }
                }

                if (cnt < 3) tmp[i][j]--; // 3개 미만이라면 얼음 녹이기
            }
        }

        return tmp;
    }
    
    private static void biggest() {
        Queue<int[]> que = new LinkedList<>();
        boolean[][] checked = new boolean[n][n];

        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                total += map[i][j]; // 남아있는 얼음의 합
                if (map[i][j] > 0 && !checked[i][j]) {
                    que.offer(new int[]{i, j});
                    checked[i][j] = true;
                    int cnt = 1; // 현재 영역의 칸의 개수

                    while (!que.isEmpty()) {
                        int[] now = que.poll();

                        for (int d = 0; d < 4; d++) {
                            int nx = now[0] + dx[d];
                            int ny = now[1] + dy[d];

                            if (nx >= 0 && nx < n && ny >= 0 && ny < n) {
                                if (map[nx][ny] > 0 && !checked[nx][ny]) {
                                    que.offer(new int[]{nx, ny});
                                    checked[nx][ny] = true;
                                    cnt++;
                                }
                            }
                        }
                    }
                    
                    max = Math.max(max, cnt);
                }
            }
        }
    }
}

 

문제를 풀면서 모든 부분 격자를 시계 방향으로 90도 회전하는 부분 때문에 꽤나 애를 먹었다.

거기다 문제를 잘못 읽어 문제에 나온 예시를 이해하는 데에도 많은 시간을 소모했다.

문제를 좀 더 꼼꼼히 읽는 습관과 구현 문제를 더 많이 풀어봐야 할 것 같다...⭐