[ 백준 / BOJ 21610 ] 마법사 상어와 비바리기 ( JAVA )

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

21610번: 마법사 상어와 비바라기

문제 설명

---

`A[r][c]` : (r,c)에 있는 바구니에 저장되어 있는 물의 양 (1$\leq$r,c$\leq$N) 1번 행과 N번 행, 1번 열과 N번 열은 연결되어 있다 👉 **범위 벗어남이 없다**

처음 비바라기 시전 ➡️ (N,1), (N,2), (N-1,1), (N-1,2)에 비구름이 생성
이제 M번의 이동 명령 : i번째 이동 명령은 방향 $d_i$과 거리 $s_i$
방향

• 1 : (0,-1)
• 2 : (-1,-1)
• 3 : (-1,0)
• 4 : (-1,1)
• 5 : (0,1)
• 6 : (1,1)
• 7 : (1,0)
• 8 : (1,-1)

이동을 명령하면

1. 모든 구름이 $d_i$방향으로 $s_i$칸 이동
2. 비가 내려 각 칸의 바구니의 물의 양 +1
3. 구름이 모두 사라짐
4. 2에서 물이 증가한 칸 (r,c)에 물복사버그 마법 시전
   -> 대각선 방향으로 거리가 1인 칸에 물이 있는 바구니 수만큼 (r,c)에 있는 바구니의 물의 양이 증가
   이때는 경계가 넘어가면 안됨
5. 바구니에 물의 양이 2 이상인 모든 칸에 구름이 생기고, 물의 양 -2, 이때 3에서 사라진 칸은 제외

풀이

---

 

1. 입력

WaterOfBucket[][] : 각 바구니의 물의 양

초기 구름의 위치 (N,1), (N,2), (N-1,1), (N-1,2)을 cloud에 저장

2. 구름 이동 & 비 내리기

MoveCloud(int d, int s)
cloud에 저장된 각 구름을 이동
다음 위치
nx = (x + N + dx[d] * s % N) % N
ny = (y + N + dy[d] * s % N) % N
이다.

음수가 나올 수 있기 때문에 N을 더하고 첫 행/열과 마지막 행/열이 연결되어있기 때문에 N으로 나누어 준다.

 

WaterOfBucket[nx][ny] += 1 해줌으로 물의 양을 증가
동일한 곳에 구름이 생기지 않게 하도록 isVisited[nx][ny] = true 해준다.

 

3. 물복사버그 마법 시전

checkDiagonal()

1. cloud의 구름들의 대각선을 확인
2. 범위가 1$\leq$x,y$\leq$N 라면 cnt += 1
3. cnt 만큼 WaterOfBucket[x][y] += cnt

4. 구름 지우기 & 구름 생성

makeCloud()
cloud = new ArrayList<>(); 로 구름 지우기

각 칸을 돌면서 물의 양이 2이상이고, !isVisited[x][y]라면
WaterOfBucket[x][y] -=2
cloud.add(new int[]{x,y})
해준다.

1, 2, 3을 M번 수행 후, 물의 양 계산

calOfWater()
각 칸을 돌면서 물의 양을 더한 후, return

코드

---

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.List;
import java.util.StringTokenizer;

public class Main_BOJ_21610_마법사_상어와_비바라기 {
    static int N, M, d, s;
    static int[][] WaterOfBucket;
    static boolean[][] isVisited;
    static List<int[]> cloud;
    static int[] dx = {0, 0, -1, -1, -1, 0, 1, 1, 1};
    static int[] dy = {0, -1, -1, 0, 1, 1, 1, 0, -1};

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer stringTokenizer = new StringTokenizer(br.readLine());

        N = Integer.parseInt(stringTokenizer.nextToken());
        M = Integer.parseInt(stringTokenizer.nextToken());

        WaterOfBucket = new int[N][N];
        for(int i = 0 ; i < N ; i++){
            stringTokenizer = new StringTokenizer(br.readLine());
            for (int j = 0; j < N; j++) {
                WaterOfBucket[i][j] = Integer.parseInt(stringTokenizer.nextToken());
            }
        }

        cloud = new ArrayList<>();
        cloud.add(new int[]{N-2,0});
        cloud.add(new int[]{N-2,1});
        cloud.add(new int[]{N-1,0});
        cloud.add(new int[]{N-1,1});

        for (int i = 0; i < M; i++) {
            stringTokenizer = new StringTokenizer(br.readLine());
            d = Integer.parseInt(stringTokenizer.nextToken());
            s = Integer.parseInt(stringTokenizer.nextToken());

            isVisited = new boolean[N][N];
            MoveCloud(d, s);
            checkDiagonal();
            makeCloud();
        }

        int result = calOfWater();
        System.out.println(result);
    }

    private static int calOfWater() {
        int sum = 0;
        for (int i = 0; i < N; i++) {
            for (int j = 0; j < N; j++) {
                sum += WaterOfBucket[i][j];
            }
        }
        return sum;
    }

    private static void makeCloud() {
        cloud = new ArrayList<>();
        for (int i = 0; i < N; i++) {
            for (int j = 0; j < N; j++) {
                if (WaterOfBucket[i][j] >= 2 && !isVisited[i][j]) {
                    WaterOfBucket[i][j] -= 2;
                    cloud.add(new int[]{i, j});
                }
            }
        }
    }

    private static void checkDiagonal() {
        for (int[] c : cloud) {
            int cnt = 0;
            for (int d = 2; d < 9; d += 2) {
                int nx = c[0] + dx[d];
                int ny = c[1] + dy[d];

                if (nx < 0 || ny < 0 || N <= nx || N <= ny) continue;
                if(WaterOfBucket[nx][ny] > 0) cnt++;
            }
            WaterOfBucket[c[0]][c[1]] += cnt;
        }
    }

    private static void MoveCloud(int d, int s) {
        for (int[] c : cloud) {
            int nx = (c[0] + N + dx[d] * s % N) % N;
            int ny = (c[1] + N + dy[d] * s % N) % N;

            isVisited[nx][ny] = true;
            WaterOfBucket[nx][ny] += 1;
            c[0] = nx;
            c[1] = ny;
        }
    }
}