[boj] 백준 20058 마법사 상어와 파이어스톰 (Java) - 시뮬레이션(배열 회전), BFS

[문제]

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

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

 

[풀이]

1. 2^L x 2^L 의 부분격자를 시계방향으로 90도 회전시킨다.

2. 3면 이상 얼음에 닿아있지 않으면 얼음의 양이 1 줄어든다. 

3. 남아있는 얼음의 양의 합과 가장 큰 덩어리의 칸의 개수를 출력한다.

 

2^L x 2^L 의 부분격자에 대해 2차원 배열 회전을 시켜줘야 한다.

2차원 배열 회전은 직접 그림을 그려서 어떻게 회전이 되는지 확인했다. 

 

1	2	3	4
5	6	7	8
9	10	11	12
13	14	15	16

 

위 4x4 격자를 시계방향으로 90도 회전 시키면 아래와 같다.

 

13	9	5	1
14	10	6	2
15	11	7	3
16	12	8	4

 

새로 회전한 배열을 temp, 기존 배열을 board라고 두었다.

2차원 반복문을 돌렸을 때 temp[i][j]에 들어가야 할 board 값이 뭔 지 찾아보면 다음과 같다.

temp의 열이 0->1->2->3으로 증가하는 값을 보면 13->9->5->1이다. 이를 기존 배열에서 확인하면 행의 값이 3->2->1->0으로 줄어들고 있음을 확인할 수 있다. 즉 temp의 j가 0->1->2->3으로 증가할 때 board의 i는 3->2->1->0으로 줄어든다. 따라서 일반화하면 N-1-j 로 나타낼 수 있다. 

temp의 열이 증가하는 13->9->5->1의 기존 배열에서의 열 값은 0->0->0->0 이다. 다음 행인 14->10->6->2의 경우 1->1->1->1 이다. 즉  temp의 j가 0->1->2->3으로 증가할 때 board의 j는 0->0->0->0 이므로 이를 일반화하면 i로 나타낼 수 있다.

코드로 보면 다음과 같다.

 

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

 

이 문제에서는 격자를 나눈 부분격자마다 회전을 시켜줬기 때문에 시작 지점인 r, c와 부분격자의 크기인 w에 맞게 반영해주는 과정이 추가적으로 필요하다.

 

그리고 주의해야 할 점!!! 얼음이 녹을 때, 얼음은 동시에 녹는다. 즉, 회전 시킨 배열인 board를 얼음을 녹일 때 바로 사용한다면, for문을 돌면서 녹은 얼음이 있을 때, 그 녹은 얼음이 다른 얼음이 녹는지 판단할 때도 반영이 되는 문제가 발생한다. 따라서 temp 배열을 새로 복사해서 사용해야 한다.

 

덩어리가 큰 얼음을 구할 때는 BFS를 돌면서 크기를 비교해주면 된다.

 

[코드]

 

package 시뮬레이션;

import java.util.*;
import java.io.*;

public class boj_20058_java{
    static int n, q;
    static int[][] board;
    static int[] order;
    static int len;
    static int[] dr = {0, 0, -1, 1};
    static int[] dc = {-1, 1, 0, 0};
    static boolean[][] visited;
    static int sum, count;
    public static class Point{
        int r, c;
        Point(int r, int c){
            this.r = r;
            this.c = c;
        }
    }
    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());

        len = (int)Math.pow(2, n);//2^n
        board = new int[len][len];
        for(int i=0; i<len; i++){
            st = new StringTokenizer(br.readLine());
            for(int j=0; j<len; j++){
                board[i][j] = Integer.parseInt(st.nextToken());
            }
        }

        order = new int[q];
        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++){
            //격자를 나누고 시계 방향 90도 회전시킨다
            board = divide(order[i]);
            //얼음이 있는 칸 3개 이상과 인접해있지 않은 칸은 얼음양이 1 줄어든다
            board = melt();
        }

        //남아있는 얼음의 합, 가장 큰 덩어리가 차지하는 칸의 개수
        for(int i=0; i<len; i++){
            for(int j=0; j<len; j++){
                if(board[i][j]==0) continue;
                sum += board[i][j];
            }
        }

        visited = new boolean[len][len];
        for(int i=0; i<len; i++){
            for(int j=0; j<len; j++){
                if(!visited[i][j] && board[i][j]!=0) {
                    count = Math.max(count, bfs(i, j));
            
                }
            }
        }

        System.out.println(sum);
        System.out.println(count);
        
    }

    public static int bfs(int r, int c){
        Queue<Point> q = new LinkedList<>();
        q.add(new Point(r, c));
        visited[r][c] = true;

        int cnt = 1; //칸의 개수

        while(!q.isEmpty()){
            Point p = q.poll();

            for(int i=0; i<4; i++){
                int nr = p.r + dr[i];
                int nc = p.c + dc[i];

                if(nr<0 || nc<0 || nr>=len || nc>=len || visited[nr][nc] || board[nr][nc]==0) continue;

                visited[nr][nc] = true;
                cnt++;
                q.add(new Point(nr, nc));
            }
        }

        return cnt;
    }

    public static int[][] divide(int l){
        int[][] temp = new int[len][len];

        l = (int)Math.pow(2, l);

        //배열 시계 방향 90도 회전
        for(int i=0; i<len; i+=l){
            for(int j=0; j<len; j+=l){
                rotate(i, j, l, temp);
            }
        }

        return temp;
    }

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

    //얼음은 동시에 녹음
    public static int[][] melt(){

        int[][] temp = new int[len][len];
        for (int i=0; i<len; i++) 
            temp[i] = Arrays.copyOf(board[i], len); //얼음이 녹은 걸 반영해줄 배열

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

                if(board[i][j]==0) continue;

                int cnt = 0;
                for(int k=0; k<4; k++){
                    int nr = i + dr[k];
                    int nc = j + dc[k];

                    if(nr<0 || nc<0 || nr>=len || nc>=len || board[nr][nc]==0) continue;

                    cnt++;
                }

                if(cnt<=2){
                    //얼음이 녹음
                    temp[i][j]--;
                }
            }
        }

        return temp;
    }
        
}