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

 

이번 문제도 구현문제이다. 문제에 나와있는대로 풀면되고, 어떻게 90도로 돌릴지에 대해서만 잘 생각하면 금방풀 수 있는 문제였지만, 나는 그 부분이 오래 걸려서 문제 푸는데 오래 걸렸다.

구현, 시뮬레이션 문제는 나에게는 약간 가성비가 떨어지는 느낌쓰,,, 자존감도 떨어뜨리는,,,, 그래서 가끔씩 풀기 싫지만, 코테에 가장 많이 나오는 문제이기 때문에 더더더더더 많이 풀어서, 구현이 문제가 편한 사람이 되즈아~~~

 

👨‍🏫 풀이

rotate를 먼저하자. rotate를 할때는 L X L 씩 잘라서 하면 된다.

다음 rotate된 후에 위치는 행은 사각형 왼쪽 위 꼭짓점의 행에 + 0,1,2,3,4,...L-1을 차례로 더해주면 나오고, 열은 사각형 왼쪽 위 꼭짓점 열 + L - 행이 커지는 변수(i) - 1 을 해주면 구할 수 있다.

다 구한 후에는 이전 배열에 저장을 해준다.

녹은 얼음을 계산하면 되기 때문에, 얼음은 동시에 녹기 때문에 현재 크기로만 현재 위치에서 상하좌우를 비교해서 얼음이 2개이하면 얼음을 녹여준다.

 

Q만큼 사이클을 돌린후에는 모든 얼음의 크기는 그냥 다 더하면 되고, 덩어리는 BFS로 각 덩어리의 크기들을 구해서 가장 큰 덩어리의 크기를 반환해준다.

 

👨🏻‍💻 코드

package 번20058;

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 {
    static int[][] A;
    static int[][] temp; // rotate할 때, 얼음 줄일때 저장할 배열
    static int[] mR = {0,0,1,-1};
    static int[] mC = {1,-1,0,0};
    static int Q;
    static int N;
    static boolean[][] isVisited;
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        N = (int) Math.pow(2,Integer.parseInt(st.nextToken()));
        Q = Integer.parseInt(st.nextToken());
        A = new int[N][N];
        temp = new int[N][N];
        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());
        while(Q-- != 0){
            int L = (int) Math.pow(2,Integer.parseInt(st.nextToken()));
            for(int i = 0 ; i < N ; i += L){
                for(int j = 0 ; j < N ; j += L){
                    rotate(i,j,L);
                }
            }
            save();
            melt();
            save();
        }
        System.out.println(iceSum());
        int part = 0;
        isVisited = new boolean[N][N];
        for(int i = 0 ; i < N ; i++){
            for(int j = 0 ; j < N ; j++){
                if(!isVisited[i][j] && A[i][j] != 0){
                    part = Math.max(part,bfs(i,j));
                }
            }
        }
        System.out.println(part);
    }
    static class Node{
        int r,c;

        public Node(int r, int c) {
            this.r = r;
            this.c = c;
        }
    }
    private static int bfs(int r, int c) {
        Queue<Node> q = new LinkedList<>();
        q.add(new Node(r,c));
        isVisited[r][c] = true;
        int cnt = 0;
        while(!q.isEmpty()){
            Node n = q.poll();
            cnt++;
            for(int i = 0 ; i < 4 ; i++){
                int nR = n.r + mR[i]; int nC = n.c + mC[i];
                if(nR < 0 || nR >= N || nC < 0 || nC >= N) continue;
                if(A[nR][nC] == 0 || isVisited[nR][nC]) continue;
                isVisited[nR][nC] = true;
                q.add(new Node(nR,nC));
            }
        }

        return cnt;
    }

    private static long iceSum() {
        long sum = 0L;
        for(int i = 0 ; i < N ; i++){
            for(int j = 0 ; j < N ; j++){
                sum += A[i][j];
            }
        }
        return sum;
    }

    private static void melt() {
        for(int i = 0 ; i < N ; i++){
            for(int j = 0 ; j < N ; j++){
                int cnt = 0;
                if(A[i][j] == 0) continue;
                for(int k = 0 ; k < 4 ; k++){
                    int nR = i + mR[k]; int nC = j + mC[k];

                    if(nR < 0 || nC < 0 || nR >= N || nC >= N) continue;
                    if(A[nR][nC] == 0) continue;
                    cnt++;
                }
                if(cnt <= 2){
                    temp[i][j] = A[i][j] - 1;
                }
            }
        }
    }

    private static void save() {
        for(int i = 0 ; i < N ; i++){
            for(int j = 0 ; j < N ; j++){
                A[i][j] = temp[i][j];
            }
        }
    }

    private static void rotate(int r, int c, int L) {
        for(int i = 0 ; i < L ; i++){
            for(int j = 0 ; j < L ; j++){
                temp[r+j][c + L - i - 1] = A[r+i][c+j];
            }
        }
    }

}