회전하는 빙하 (JAVA)

📖 문제

코드트리 | 코딩테스트 준비를 위한 알고리즘 정석

 

 

💡  풀이 방식

• 시뮬레이션 + BFS

필요 자료구조
- dx/dy 배열
- N, Q, len (격자 크기 저장 변수)
- 격자 값 저장하는 2차원 int형 배열 grid
- 결과값 저장하는 임시 2차원 int형 배열 nextGrid
- BFS할 때 방문 표시할 2차원 boolean형 배열

 

- N과 Q, 격자 배열의 값을 입력받는다.

 

- Q번 동안 레벨을 입력받고, 레벨에 맞춰 회전시키고, 얼음을 녹인다.

> 회전시키는 메소드 rotate

     1. 회전 이후의 상태를 저장하는 배열을 0으로 초기화한다.

     2. 회전시킨다.

      2-1) 격자를 회전시킬 왼쪽 위 모서리 위치를 잡는다.

      2-2) 2-1에서 구한 왼쪽 위 모서리 위치에서부터 2^*(L -1) 크기만큼 4등분해 회전시킨다. 🔔

         ㄴ 4등분했을 때 왼쪽     위에 있는    칸들은  오른쪽 0 (0, 1)으로 이동

         ㄴ 4등분했을 때 오른쪽 위에 있는    칸들은  아래쪽 1 (1, 0)으로 이동

         ㄴ 4등분했을 때 오른쪽 아래에 있는 칸들은 왼쪽     2 (-1, 0으로 이동

         ㄴ 4등분했을 때 왼쪽     아래에 있는 칸들은 위쪽     3 (0, -1)으로 이동

 

    3. 회전한 결과를 반영해야 하므로 원본 배열에 다시 저장한다.

 

> 얼음 녹이는 메소드 melt

   1. 녹은 이후 상태를 저장할 배열 nextGrid의 모든 값을 0으로 초기화한다.

   2. 칸의 값이 0이 아니고, 주변 얼음 갯수가 3개 미만이라면 얼음 갯수를 -1한 값을 결과 배열 nextGrid에 저장한다.

     / 그게 아니라면, nextGrid 배열에 grid 값을 그대로 저장한다.

 

   3. 녹인 결과를 반영해야 하므로 원본 배열에 다시 저장한다.

 

 

- 남은 빙하 총량 계산한다. > 배열 내 모든 값을 더해 출력한다.

- 가장 큰 크기 갖는 얼음군집 크기 계산한다. > BFS로 각 군집 크기를 구하고 최댓값과 비교해 갱신한다.

 

 

 

🔺 코드

import java.util.*;
import java.io.*;
 
public class Main {
    static int[] dx = {0,1,-1,0};   // 오른쪽, 아래, 위 왼쪽
    static int[] dy = {1,0,0,-1};
    
    static int N, Q, len;
    static int[][] grid, nextGrid;
    static boolean[][] visited;
    static int max = 0;
 
    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);
        grid = new int[len][len];
        nextGrid = new int[len][len];
 
        for(int i = 0 ; i < len ; i++) {
            st = new StringTokenizer(br.readLine(), " ");
            for(int j = 0 ; j < len ; j++) {
                grid[i][j] = Integer.parseInt(st.nextToken());
            }
        }
 
        st = new StringTokenizer(br.readLine(), " ");
        while(Q --> 0) {
            int lv = Integer.parseInt(st.nextToken());
 
            // 1. 레벨에 맞춰 회전시키기
            if(lv > 0)
                rotate(lv);
 
            // 2. 얼음 녹이기
            melt();
        }
 
        // [출력하기]     
        // 1. 남은 빙하 총량 계산하기
        int sum = 0;
        for(int i = 0 ; i < len ; i++) {
            for(int j = 0 ; j < len ; j++) {
                sum += grid[i][j];
            }
        }
        System.out.println(sum);
 
        // 2. 가장 큰 크기 갖는 얼음군집 크기 (없으면 0) -> BFS
        visited = new boolean[len][len];
        for(int i = 0 ; i < len ; i++) {
            for(int j = 0 ; j < len ; j++) {
                if(!visited[i][j] && grid[i][j] != 0) {
                    visited[i][j] = true;
                    max = Math.max(max, bfs(i, j));
                }
            }
        }
        System.out.println(max);
    }
 
    // 회전시키는 메소드
    private static void rotate(int lv) {
        // 1. 회전 이후 상태 저장할 배열을 0으로 초기화
        initialize();
 
        int boxSize  = (int)Math.pow(2, lv);
        int halfSize = (int)Math.pow(2, lv-1);
 
        // 2. 회전하기
        // 2-1) 왼쪽 위 모서리 위치 잡기
        for(int i = 0 ; i < len ; i += boxSize) {
            for(int j = 0 ; j < len ; j += boxSize) {
                // 2-2) 🔔 움직여야 하는 크기 격자 & 왼쪽 위 모서리를 잡아 알맞은 방향으로 이동시킴
                move(i,            j,            halfSize, 0);    // 오른쪽
                move(i,            j + halfSize, halfSize, 1);    // 아래
                move(i + halfSize, j,            halfSize, 2);    // 위
                move(i + halfSize, j + halfSize, halfSize, 3);    // 왼쪽
            }
        }
 
        // 3. rotate 이후 결과를 grid 배열로 가져오기
        for(int i = 0 ; i < len ; i++) {
            for(int j = 0 ; j < len ; j++) {
                grid[i][j] = nextGrid[i][j];
            }
        }
    }
 
    // 🔔 (sr, sc)에서 halfSize 크기의 격차를 dir 방향으로 이동시키는 메소드
    private static void move(int sr, int sc, int halfSize, int dir) {
        for(int i = sr ; i < sr + halfSize ; i++) {
            for(int j = sc ; j < sc + halfSize ; j++) {
                int nx = i + dx[dir] * halfSize;
                int ny = j + dy[dir] * halfSize;
 
                if(!inRange(nx, ny))    continue;
                nextGrid[nx][ny] = grid[i][j];
            }
        }
    }
 
    // 얼음 녹이는 메소드 (브루트포스)
    private static void melt() {
        // 1. 녹은 이후 상태 저장할 배열을 0으로 초기화
        initialize();
 
        // 2. 얼음 녹이기
        for(int i = 0 ; i < len ; i++) {
            for(int j = 0 ; j < len ; j++) {                
                if(grid[i][j] != 0 && aroundIceCnt(i, j) < 3)
                    nextGrid[i][j] = grid[i][j] - 1;
                else
                    nextGrid[i][j] = grid[i][j];
            }
        }
 
        // 3. 녹은 이후 결과를 grid 배열에 다시 저장하기
        for(int i = 0 ; i < len ; i++) {
            for(int j = 0 ; j < len ; j++) {
                grid[i][j] = nextGrid[i][j];
            }
        }
    }
 
    // 주변 얼음 개수 세는 메소드
    private static int aroundIceCnt(int x, int y) {
        int iceCnt = 0;
 
        for(int d = 0 ; d < 4 ; d++) {
            int nx = x + dx[d];
            int ny = y + dy[d];
 
            if(inRange(nx, ny) && grid[nx][ny] != 0)
                iceCnt++;
        }
 
        return iceCnt;
    }
 
    // 그룹 크기 반환하는 메소드 (BFS)
    private static int bfs(int x, int y) {
        int size = 0;
 
        Queue<int[]> q = new ArrayDeque<>();
        q.add(new int[] {x, y});
 
        while(!q.isEmpty()) {
            int[] now = q.poll();
            size++;
 
            for(int d = 0 ; d < 4 ; d++) {
                int nx = now[0] + dx[d];
                int ny = now[1] + dy[d];
 
                if(!inRange(nx, ny) || visited[nx][ny] || grid[nx][ny] == 0) continue;
 
                visited[nx][ny] = true;
                q.add(new int[] {nx, ny});
            }
        }
 
        return size;
    }
 
    // 상태 저장할 배열 0으로 초기화하는 메소드
    private static void initialize() {
        for(int i = 0 ; i < len ; i++) {
            for(int j = 0; j < len ; j++) {
                nextGrid[i][j] = 0;
            }
        }
    }
 
    private static boolean inRange(int x, int y) {
        return (0 <= x && x < len && 0 <= y && y < len);
    }
}

 

 

 

---

💦 어려웠던 점

- 왼쪽 위 모서리까지는 잡았는데 그 이후에 4등분해서 회전하는 부분을 놓치다

ㄴ 3단계 : 결과 저장할 배열을 모두 0으로 초기화하고 > 값을 넣고 > 변화된 배열을 원본 배열에 다시 저장

for(int i = 0 ; i < len ; i += boxSize) {
    for(int j = 0 ; j < len ; j += boxSize) {
        // 2-2) 움직여야 하는 크기 격자 & 왼쪽 위 모서리를 잡아 알맞은 방향으로 이동시킴
        move(i,            j,            halfSize, 0);    // 오른쪽
        move(i,            j + halfSize, halfSize, 1);    // 아래
        move(i + halfSize, j,            halfSize, 2);    // 위
        move(i + halfSize, j + halfSize, halfSize, 3);    // 왼쪽
    }
}

//(sr, sc)에서 halfSize 크기의 격차를 dir 방향으로 이동시키는 메소드
private static void move(int sr, int sc, int halfSize, int dir) {
    for(int i = sr ; i < sr + halfSize ; i++) {
        for(int j = sc ; j < sc + halfSize ; j++) {
            int nx = i + dx[dir] * halfSize;
            int ny = j + dy[dir] * halfSize;

            if(!inRange(nx, ny))    continue;
            nextGrid[nx][ny] = grid[i][j];
        }
    }
}

 

 

 

 

1회독	2회독	3회독	4회독	5회독
V

---

(참고)

✔ 코드트리