[BOJ] 20058 마법사 상어와 파이어스톰 - Java

✨ BFS + 구현 ➔  부분 격자를 시계방향으로 90도 회전

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

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

---

📍 고려해야할 점

• 2^L * 2^L 크기의 부분 격자로 나누고 모든 부분 격자를 시계방향으로 90도 회전

• L=1일 때, 2x2의 부분격자가 시계방향으로 90도 회전
• L=2일 때, 4x4의 부분격자가 시계방향으로 90도 회전

• (x, y)칸에서 인접한 칸(상하좌우) 중 얼음이 있는 칸이 3개 미만이면 (x, y)칸 얼음의 양 1 감소
• 남아있는 얼음 중 가장 큰 덩어리가 차지하는 칸의 개수 구하기 👉 BFS

 

🕹️ 풀이과정

다른 조건들은 무난했으나 부분 격자를 시계방향으로 90도 회전하는 것은 조금 까다로웠다.

우선 메서드를 다음과 같이 나눈다.

 

• simulate()
  • 하위의 메서드를 Q번 반복하여 실행 = 마법 시전
• rotate()
  • 부분격자를 시계방향으로 90도 회전
• melting()
  • 인접하는 칸 중 얼음이 있는 칸이 3개 미만이면 얼음 1 감소
• getTotal()
  • 남아있는 얼음 합 구하기
• getMass()
  • 남아있는 얼음 덩어리 중 가장 큰 덩어리 구하기
• bfs()
  • 얼음 덩어리 구하는데 필요한 bfs 함수
• copy()
  • 얼음을 1 감소시킨 후 해당하는 결과값을 원래 배열에 반영함으로써 다음에 시전할 단계 준비 

---

 

이 함수들 중에서 rotate()과 melting() 메서드를 살펴보겠다.

---

🔹 rotate() 👉 내가 짠 코드 

static void rotate(int l){
    newA = new int[n][n];

    int[][] temp;
    int[][] newTemp;
    // l = 2^L
    for (int x = 0; x < n; x += l) {
        for (int y = 0; y < n; y += l) {

            temp = new int[l][l];
            newTemp = new int[l][l];
            for (int i = x; i < x + l; i++) {
                for (int j = y; j < y + l; j++) {
                    temp[i-x][j-y] = A[i][j];
                }
            }

            // 시계방향으로 90도 회전
            for (int i = 0; i < l; i++) {
                for (int j = 0; j < l; j++) {
                    newTemp[i][j] = temp[(l - 1) - j][i];
                }
            }

            for (int i = x; i < x + l; i++) {
                for (int j = y; j < y + l; j++) {
                    newA[i][j] = newTemp[i-x][j-y];
                }
            }
        }
    }
}

다소 복잡하게 코드를 작성했다...

나의 의도는 아래 그림처럼 부분격자를 아예 떼어놓고 생각해서 다시 반영시키는 방법이다. 

중간에 90도로 회전시키는 알고리즘은 상어중학교 문제에서 진행했던 동일한 방법으로 작성했다. (단지 시계방향으로만 바꿔줬을 뿐!)

 

 

🔸 rotate() 👉 쉬운 코드 

public 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;
}

public 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[x + i][y + j] = map[x + L - 1 - j][y + i];
        }
    }
}

 

---

🔹 melting()

static void melting(){
    Queue<Info> meltingIce = new LinkedList<>();

    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {

            if(newA[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 && ny>=0 && nx<n && ny<n && newA[nx][ny]!=0) cnt++;
            }
            if(cnt<3) meltingIce.add(new Info(i, j));
        }
    }

    while (!meltingIce.isEmpty()) {
        Info now = meltingIce.poll();
        newA[now.x][now.y]--;
    }
}

 

다른 칸들도 탐색해야하기 때문에 얼음이 1 감소하는 것을 바로 반영시키면 안된다.

그러므로 1 감소시켜야하는 칸들을 따로 Queue에 저장해주었고, 모든 칸들을 탐색한 후 Queue에 있던 좌표들을 하나씩 꺼내어 1 감소시킴으로써 한꺼번에 반영시켰다.

 

 

👩‍💻 전체 코드

 

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

public class BOJ_20058_마법사상어와파이어스톰 {
    static int N, Q, n, maxMass=0;
    static int[] L;
    static int[][] A;
    static int[][] newA;
    static boolean[][] visit;
    static int[] dx = {0, 0, 1, -1};
    static int[] dy = {1, -1, 0, 0};
    static class Info{
        int x, y;

        public Info(int x, int y) {
            this.x=x;
            this.y=y;
        }
    }

    // 마법 시전
    static void simulate(){

        for (int i = 0; i < Q; i++) {
            // #1. 부분 격자를 시계 방향으로 90도 회전
            int l = (int) Math.pow(2, L[i]);
            rotate(l);
            // #2. 인접한 칸 중 얼음이 있는 칸이 3개 미만이면 해당하는 칸 얼음의 양 1 감소
            melting();
            copy();
            // ==> Q번 시전
        }
        System.out.println(getTotal());
        System.out.println(getMass());
    }

    // 부분 격자로 나누고 모든 부분 격자를 시계방향으로 90도 회전
    static void rotate(int l){
        newA = new int[n][n];

        int[][] temp;
        int[][] newTemp;
        for (int x = 0; x < n; x += l) {
            for (int y = 0; y < n; y += l) {

                temp = new int[l][l];
                newTemp = new int[l][l];
                for (int i = x; i < x + l; i++) {
                    for (int j = y; j < y + l; j++) {
                        temp[i-x][j-y] = A[i][j];
                    }
                }

                for (int i = 0; i < l; i++) {
                    for (int j = 0; j < l; j++) {
                        newTemp[i][j] = temp[(l - 1) - j][i];
                    }
                }

                for (int i = x; i < x + l; i++) {
                    for (int j = y; j < y + l; j++) {
                        newA[i][j] = newTemp[i-x][j-y];
                    }
                }
            }
        }
    }

    // 얼음이 있는 칸 3개 또는 그 이상과 인접해 있지 않은 칸 = 인접한 칸 중 얼음이 있는 칸이 3개 미만--> 얼음의 양 1 감소
    static void melting(){
        Queue<Info> meltingIce = new LinkedList<>();

        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {

                if(newA[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 && ny>=0 && nx<n && ny<n && newA[nx][ny]!=0) cnt++;
                }
                if(cnt<3) meltingIce.add(new Info(i, j));
            }
        }

        while (!meltingIce.isEmpty()) {
            Info now = meltingIce.poll();
            newA[now.x][now.y]--;
        }
    }

    // 남아있는 얼음 A[r][c]의 합
    static int getTotal(){
        int total = 0;
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                if(A[i][j]!=0) total+=A[i][j];
            }
        }
        return total;
    }

    // 남아있는 얼음 중 가장 큰 덩어리가 차지하는 칸의 개수 --> BFS
    static int getMass(){
        visit = new boolean[n][n];

        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                if (!visit[i][j] && A[i][j] != 0) {
                    bfs(i, j);
                }
            }
        }
        return maxMass;
    }

    static void bfs(int x, int y){
        Queue<Info> queue = new LinkedList<>();
        queue.add(new Info(x, y));
        visit[x][y]=true;
        int cnt=1;

        while (!queue.isEmpty()) {
            Info now = queue.poll();

            for (int i = 0; i < 4; i++) {
                int nx = now.x + dx[i];
                int ny = now.y + dy[i];

                if (nx >= 0 && ny >= 0 && nx < n && ny < n && !visit[nx][ny]) {
                    if (newA[nx][ny] != 0) {
                        visit[nx][ny] = true;
                        queue.add(new Info(nx, ny));
                        cnt++;
                    }
                }
            }
        }
        maxMass = Math.max(maxMass, cnt);
    }

    static void copy(){
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                A[i][j] = newA[i][j];
            }
        }
    }


    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);
        A = new int[n][n];
        L = new int[Q];

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

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

        simulate();
    }
}