BOJ 20058 - 마법사 상어와 파이어 스톰(Java)

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

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

 

풀이

1. 명령의 수 만큼 반복, 명령 L에 대해 진행

    1) 2^L X 2^L로 구역 나누기, 구역 별 회전

    2) 인근 지역에 얼음이 없다면 얼음줄이기

        - 동서남북 4방향에 대해 얼음이 남은 인접 칸의 개수 확인

        - 인접 칸의 개수가 3이상이 아니라면 해당 칸의 얼음을 1 줄임

 

2. 1이 끝나면 남아있는 얼음의 합, 전체 영역 중 가장 큰 덩어리를 탐색

 

명령 L에 따른 구역 나누기/회전

L(Level)에 따른 구역 나누기

L에 따라 나눠지는 구역의 크기가 결정 len = 2^L

이렇게 나눠진 구역 마다 90도 회전 

private static void divideArea(int level) {
    int len = (int) Math.pow(2, level);
    
    for (int y = 0; y < LEN; y += len) {
        for (int x = 0; x < LEN; x += len) {
            rotate(y, x, level);
        }
    }
}

현재 구역 90도 회전

구역의 전체를 90도 회전, 구역의 바깥 -> 안쪽으로 진행

len이 2이상인 동안 반복 (최초 len = 2^level)

    - 현재 단계의 회전이 진행된 후, y와 x를 1씩 증가하고 회전할 구역의 길이(len)를 2 감소

private static void rotate(int sY, int sX, int level) {
    int y = sY;
    int x = sX;
    List<Integer> temp;
    int len = (int) Math.pow(2, level);
    
    while (len >= 2) {
        temp = new ArrayList<>();
        int j = x;
        int i = y + len-1;
        
        for (int _i = y; _i < y + len - 1; _i++) temp.add(map[_i][x]);
        for (int _i = y; _i < y + len - 1; _i++) map[_i][x] = map[y + len -1][j++];
        for (int _j = x; _j < x + len - 1; _j++) map[y + len-1][_j] = map[i--][x + len-1];
        for (int _i = y + len - 1; _i >= y; _i--) map[_i][x + len-1] = map[y][j--];
        
        int idx=0;
        for(int _j = x + len - 1; _j > x; _j--) map[y][_j] = temp.get(idx++);
        y++;
        x++;
        len-=2;
    }
}

 

 

인근 지역 확인 및 얼음 줄이기

현재 위치에 대해 얼음을 녹여야하는지 확인

private static boolean isReduce(int i, int j) {
    int cnt = 0;
    // 동서남북 4방향에 대해 인접한 칸에 얼음이 있는지 확인하고 얼음이 있는 칸의 개수를 확인
    for (int d = 0; d < 4; d++) {
        int ny = i + dy[d];
        int nx = j + dx[d];
        if (!isRange(ny, nx)) continue;
        if (map[ny][nx] > 0) cnt++;
    }
    // 얼음이 있는 칸이 3이상이면 얼음을 녹이지 않음 -> false
    if (cnt >= 3) return false;
    // 3미만이라면 얼음을 녹임 -> true
    else return true;
}

모든 위치에 대해 이러한 확인을 진행

얼음이 녹는 칸을 List에 삽입, sum--

    * sum = (최초 입력 받을 때)얼음의 총합

이후, List를 순회하여 해당 칸의 얼음을 1씩 줄임

private static void reduceIce() {
    List<Pair> list= new ArrayList<>();
    for (int i = 0; i < LEN; i++) {
        for (int j = 0; j < LEN; j++) {
            if (map[i][j] == 0) continue;
            if (isReduce(i, j)) {
                sum--;
                list.add(new Pair(i ,j));
            }
        }
    }
    // List 순회 한번에 얼음을 녹임
    for (int i = 0; i < list.size(); i++) {
        map[list.get(i).y][list.get(i).x]--;
    }
}

 

가장 큰 덩어리 찾기

현재 위치에 대해 bfs 탐색

인근 위치에 대해 얼음이 있는 칸을 queue에 삽입, 삽입마다 방문했다는 것을 갱신(boolean 이차원 배열)

queue를 빼낼때 마다 size를 1씩 증가

해당 위치의 bfs가 끝날때, size의 값이 현재 위치에 대한 덩어리의 크기

private static int bfs(int i, int j) {
    int size = 0;
    visit[i][j] = true;
    LinkedList<Pair> q = new LinkedList<>();
    q.add(new Pair(i, j));

    while (!q.isEmpty()) {
        Pair now = q.poll();
        int y = now.y;
        int x = now.x;
        size++;

        for (int d = 0; d < 4; d++) {
            int ny = y + dy[d];
            int nx = x + dx[d];
            if (!isRange(ny, nx)) continue;
            if (visit[ny][nx] || map[ny][nx] == 0) continue;
            visit[ny][nx] = true;
            q.add(new Pair(ny, nx));
        }
    }
    return size;
}

이러한 탐색을 모든 칸에 대해 진행

    - bfs 탐색마다 최대값 비교/갱신

visit[][]에 true라면 이전 위치에서 이미 방문을 한 칸이기 때문에 탐색할 필요 X

private static int searchBiggestArea() {
    int max = 0;
    visit = new boolean[LEN][LEN];
    for (int i = 0; i < LEN; i++) {
        for (int j = 0; j < LEN; j++) {
            // 현재 위치 얼음의 수가 0이거나 이미 방문 했다면 pass
            if (map[i][j] == 0 || visit[i][j]) continue;
            int size = bfs(i, j);
            max = Math.max(size, max);
        }
    }
    return max;
}

---

전체 코드

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

public class Main {
    static int N, Q, LEN;
    static int[][] map;
    static boolean[][] visit;
    static int sum = 0;
    static int[] dy = {0, 1, 0, -1};
    static int[] dx = {1, 0, -1, 0};

    static class Pair {
        int y, x;

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

    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());
        LEN = (int) Math.pow(2, N);
        map = new int[LEN][LEN];

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

        st = new StringTokenizer(br.readLine());
        for (int i = 0; i < Q; i++) {
            int level = Integer.parseInt(st.nextToken());
            divideArea(level);
            reduceIce();
        }

        System.out.println(sum);
        System.out.println(searchBiggestArea());
    }
    // level에 따른 회전 구역 정하기
    private static void divideArea(int level) {
        int len = (int) Math.pow(2, level);
        for (int y = 0; y < LEN; y += len) {
            for (int x = 0; x < LEN; x += len) {
                // 정해진 구역 90도 회전
                rotate(y, x, level);
            }
        }
    }
    
    // 해당 구역 전체를 90도 회전 
    private static void rotate(int sY, int sX, int level) {
        int y = sY;
        int x = sX;
        List<Integer> temp;
        int len = (int) Math.pow(2, level);
        // 해당구역의 안쪽까지 90도 회전을 위해 len을 2씩 감소, len이 2이상인 동안 지속
        while (len >= 2) {
            temp = new ArrayList<>();
            int j = x;
            int i = y + len-1;
            for (int _i = y; _i < y + len -1; _i++) temp.add(map[_i][x]);
            for (int _i = y; _i < y + len-1; _i++)
                map[_i][x] = map[y + len -1][j++];
            for (int _j = x; _j < x + len-1; _j++)
                map[y + len-1][_j] = map[i--][x + len-1];
            for (int _i = y + len - 1; _i >= y; _i--)
                map[_i][x + len-1] = map[y][j--];
            int idx=0;
            for(int _j=x+len-1;_j>x;_j--)
                map[y][_j]=temp.get(idx++);
            y++;
            x++;
            len-=2;
        }
    }
    
    // 가장 큰 덩어리를 탐색
    private static int searchBiggestArea() {
        int max = 0;
        visit = new boolean[LEN][LEN];
        for (int i = 0; i < LEN; i++) {
            for (int j = 0; j < LEN; j++) {
                if (map[i][j] == 0 || visit[i][j]) continue;
                // 해당 위치에서의 덩어리 크기를 탐색(bfs)
                int size = bfs(i, j);
                // 이전까지의 최대 덩어리 크기와 비교/갱신
                max = Math.max(size, max);
            }
        }
        return max;
    }
    
    // 해당 위치의 덩어리 크기 탐색
    private static int bfs(int i, int j) {
        int size = 0;
        visit[i][j] = true;
        LinkedList<Pair> q = new LinkedList<>();
        q.add(new Pair(i, j));

        while (!q.isEmpty()) {
            Pair now = q.poll();
            int y = now.y;
            int x = now.x;
            size++;

            for (int d = 0; d < 4; d++) {
                int ny = y + dy[d];
                int nx = x + dx[d];
                if (!isRange(ny, nx)) continue;
                if (visit[ny][nx] || map[ny][nx] == 0) continue;
                visit[ny][nx] = true;
                q.add(new Pair(ny, nx));
            }
        }
        return size;
    }
    
    // 얼음 녹이기
    private static void reduceIce() {
        List<Pair> list= new ArrayList<>();
        for (int i = 0; i < LEN; i++) {
            for (int j = 0; j < LEN; j++) {
                if (map[i][j] == 0) continue;
                //해당 위치 얼음이 녹는지 확인
                if (isReduce(i, j)) {
                    sum--;
                    // 한번에 녹이기 위함
                    // 녹는 얼음에 대한 좌표 List에 추가
                    list.add(new Pair(i ,j));
                }
            }
        }
        // List에 담긴 위치의 얼음을 감소
        for (int i = 0; i < list.size(); i++) {
            map[list.get(i).y][list.get(i).x]--;
        }
    }
    
    // 해당 위치에 얼음이 녹는지 확인
    private static boolean isReduce(int i, int j) {
        int cnt = 0;
        for (int d = 0; d < 4; d++) {
            int ny = i + dy[d];
            int nx = j + dx[d];
            if (!isRange(ny, nx)) continue;
            if (map[ny][nx] > 0) cnt++;
        }
        // 인근 얼음의 개수가 3 이상이면 얼음이 안녹음 -> false
        if (cnt >= 3) return false;
        // 이외에는 얼음이 녹음 -> true
        else return true;
    }
   
    // 현재 위치가 정상 범위인지 확인
    private static boolean isRange(int i, int j) {
        if (i < 0 || j < 0 || i >= LEN || j >= LEN) return false;
        else return true;
    }

}