[백준]JAVA - 20058번: 마법사 상어와 파이어스톰

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

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

풀이

요즘 마법사 상어 시리즈를 풀어보고있는데 파이어스톰 마법을 배웠다고 한다...

위 문제는 아래와 같은 과정을 거친다.

 

1. 파이어스톰 단계를 L이라고 가정했을 때, (0, 0)을 시작으로 $2^{L}$x$2^{L}$ 크기의 부분 격자로 나눈다.
2. 모든 부분 격자를 시계 방향으로 90도 회전시킨다.
3. 특정 칸에서 인접해있는 칸 중 얼음이 존재하는 칸이 3개 미만이라면 특정 칸의 얼음의 양이 1 줄어든다.
4. 위 과정을 Q번 반복한다.

1. 파이어스톰 단계를 L이라고 가정했을 때, (0, 0)을 시작으로 $2^{L}$x$2^{L}$ 크기의 부분 격자로 나눈다.

public static void fireStorm(int step) {
    tmp = new int[mapSize][mapSize];
        
    for (int i=0; i<mapSize; i+=step) {
        for (int j=0; j<mapSize; j+=step) {
            rotate(i, j, step); // 회전
        }
    }
        
    map = tmp;
}

 

2. 모든 부분 격자를 시계 방향으로 90도 회전시킨다.

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

부분 격자가 만들어지면 위 그림처럼 이동한다. 

회전하는 식을 찾는데 엄청나게 오랜 시간을 소비했다..

 

3. 특정 칸에서 인접해있는 칸 중 얼음이 존재하는 칸이 3개 미만이라면 특정 칸의 얼음의 양이 1 줄어든다.

public static void meltIce() {
    tmp = new int[mapSize][mapSize];
        
    for (int i=0; i<mapSize; i++) {
        for (int j=0; j<mapSize; 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 || ny < 0 || nx > mapSize-1 || ny > mapSize-1) continue;
                    
                if (map[nx][ny] > 0) {
                    cnt++;
                }
            }
                
            if (cnt < 3) {
                tmp[i][j] = map[i][j] - 1;
            } else {
                tmp[i][j] = map[i][j];
            }
        }
    }
        
    map = tmp;
}

bfs를 이용해서 인접하고 있는 얼음칸을 찾는다. 3개 미만이면 얼음양을 1 줄이고, 그렇지않다면 그대로 두면 된다. bfs를 돌리는 과정에서 값이 변경되면 얼음칸이었던 곳이 아니게 될 수 있기 때문에 임시 배열을 만들어서 bfs가 끝나면 다시 map 배열에 복사한다.

 

<최종코드>

import java.io.*;
import java.util.*;
 
public class Main {
    static int N, mapSize, max_ice = 0;
    static int[][] map, tmp;
    static int[] dx = {0, 1, 0, -1};
    static int[] dy = {1, 0, -1, 0};
    static boolean[][] visited;
    
    public static class Ice {
        int x, y;
        
        public Ice (int x, int y) {
            this.x = x;
            this.y = y;
        }
    }
    
    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());
        int Q = Integer.parseInt(st.nextToken());
        mapSize = (int) Math.pow(2, N);
        
        map = new int[mapSize][mapSize];
        for (int i=0; i<mapSize; i++) {
            st = new StringTokenizer(br.readLine());
            for (int j=0; j<mapSize; j++) {
                map[i][j] = Integer.parseInt(st.nextToken());
            }
        }
        
        int[] step = new int[Q];
        st = new StringTokenizer(br.readLine());
        for (int i=0; i<Q; i++) {
            step[i] = Integer.parseInt(st.nextToken());
        }
        
        for (int i=0; i<Q; i++) {
            fireStorm((int) Math.pow(2, step[i]));
            meltIce();
        }
        
        int ans = 0;
        visited = new boolean[mapSize][mapSize];
        for (int i=0; i<mapSize; i++) {
            for (int j=0; j<mapSize; j++) {
                    ans+= map[i][j];
                if (!visited[i][j] && map[i][j] > 0) {
                    findIce(i, j);
                }
            }
        }
        
        System.out.println(ans);
        System.out.println(max_ice);
    }
    
    public static void fireStorm(int step) {
        tmp = new int[mapSize][mapSize];
        
        for (int i=0; i<mapSize; i+=step) {
            for (int j=0; j<mapSize; j+=step) {
                rotate(i, j, step);
            }
        }
        
        map = tmp;
    }
    
    public static void rotate(int x, int y, int level) {
        for (int i=0; i<level; i++) {
            for (int j=0; j<level; j++) {
                tmp[x+i][y+j] = map[x+level-j-1][y+i];
            }
        }
    }
    
    public static void meltIce() {
        tmp = new int[mapSize][mapSize];
        
        for (int i=0; i<mapSize; i++) {
            for (int j=0; j<mapSize; 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 || ny < 0 || nx > mapSize-1 || ny > mapSize-1) continue;
                    
                    if (map[nx][ny] > 0) {
                        cnt++;
                    }
                }
                
                if (cnt < 3) {
                    tmp[i][j] = map[i][j] - 1;
                } else {
                    tmp[i][j] = map[i][j];
                }
            }
        }
        
        map = tmp;
    }
    
    public static void findIce(int x, int y) {
        int ice = 1;
        
        Queue<Ice> q = new LinkedList<>();
        q.add(new Ice(x, y));
        visited[x][y] = true;
        
        while (!q.isEmpty()) {
            Ice now = q.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 > mapSize-1 || ny > mapSize-1 || visited[nx][ny] || map[nx][ny] == 0) continue;
                
                q.add(new Ice(nx, ny));
                visited[nx][ny] = true;
                ice++;
            }
        }
        
        max_ice = Math.max(ice, max_ice);
    }
}