[백준 Baekjoon] 21610번 마법사 상어와 비바라기 - JAVA

[백준 Baekjoon] 21610번 마법사 상어와 비바라기 - JAVA

---

문제 풀이

문제에서 주어진 격자는 (1, 1)부터 (N, N)의 크기이지만, 저는 (0, 0)부터 (N-1, N-1)의 크기로 만들어 사용하였습니다.

방향 이동 또한 1부터가 아닌 0부터 순서대로 하였습니다.

 

구름은 이동하고 비가 내린 다음 이동하기 때문에 큐를 사용하였습니다.

처음 구름은 (N-1, 0), (N-2, 1), (N-2, 0), (N-2, 1) 4칸에 존재하여 4칸을 큐에 추가합니다.

 

1. 구름이 di 방향으로 si칸 이동한다.

큐에 존재하는 모든 구름에 대하여 x, y값을 변경해줍니다.

// 구름이 di 방향으로 si칸 이동
cloud.x = (N + cloud.x + dx[d] * (s % N)) % N;
cloud.y = (N + cloud.y + dy[d] * (s % N)) % N;

N번 이상 이동할 경우 N으로 나머지 연산한 결과와 동일함으로 (s % N)을 해줍니다.

dx[d]는 방향으로 si(s % N)만큼 dx[d] * (s % N)을 통해 이동해줍니다.

행과 열의 0번째 칸이 N-1번째 칸과 이어져있기 때문에 격자를 벗어나는 경우를 처리해주어야 합니다.

N + cloud.x + dx[d] * (s % N)) % N 에서 앞에 N을 더해주고 마지막에 N으로 나머지 연산하여 이어져있도록 하였습니다.

 

2. 각 구름에서 비가 내려 구름이 있는 칸의 바구니에 저장된 물의 양이 1 증가한다.

1에서 이동한 구름에 대하여 1씩 증가시켜 줍니다.

 

3. 구름이 모두 사라진다.

2까지 수행한 뒤, 4를 수행하면서 큐에서 구름을 하나씩 제거합니다.

3에서 사라지는 칸은 5에서 새로 생기는 구름에 포함되면 안 되므로 visit배열에 체크를 해줍니다.

// 구름이 모두 사라진다.
Cloud cloud = clouds.poll();

// 구름이 생기는 칸은 3에서 사라진 칸이 아니어야 한다.
visit[cloud.x][cloud.y] = true;

4. 2에서 물이 증가한 칸 (r, c)에 물복사버그 마법을 시전 한다.

대각선 방향으로 거리가 1인 칸에 물이 있는 바구니의 수만큼 (r, c)에 있는 바구니의 물이 양이 증가한다.

큐에서 꺼낸 구름의 대각선 방향을 검사합니다. 8개의 방향 중 홀수 방향을 검사합니다.

이때 경계를 넘어가는 칸은 대각선 방향으로 거리가 1인 칸이 아니므로 격자를 벗어나는지 검사합니다.

if (diagonalX < 0 || diagonalY < 0 || diagonalX >= N || diagonalY >= N) continue;

대각선 방향으로 거리가 1인 칸에 물이 있는 바구니의 수만큼 바구니의 물 양을 증가시켜줍니다.

 

5. 바구니에 저장된 물의 양이 2 이상인 모든 칸에 구름이 생기고, 물의 양이 2 줄어든다.

3에서 구름이 사라진 칸이 아니며 물의 양이 2 이상인 칸인지 검사합니다.

if (!visit[i][j] && grid[i][j] >= 2)

해당 칸들을 큐에 추가하고 물의 양을 2 감소시켜줍니다.

 

3에서 사라진 구름인지 검사를 완료하였으므로, 다음 사라지는 구름을 체크하기 위해 visit배열을 초기화해줍니다.

 

소스코드

import java.io.BufferedReader;
import java.io.FileReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;

public class Main {
    public static int N;
    public static int[][] grid;
    public static boolean[][] visit;

    public static Queue<Cloud> clouds = new LinkedList<>();

    public static int[] dx = {0, -1, -1, -1, 0, 1, 1, 1};
    public static int[] dy = {-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 st = new StringTokenizer(br.readLine());
        N = Integer.parseInt(st.nextToken());
        int M = Integer.parseInt(st.nextToken());

        grid = new int[N][N];
        visit = new boolean[N][N];

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

        // 처음 구름은 (N-1, 0), (N-2, 1), (N-2, 0), (N-2, 1) 4칸에 존재
        clouds.add(new Cloud(N - 1, 0));
        clouds.add(new Cloud(N - 1, 1));
        clouds.add(new Cloud(N - 2, 0));
        clouds.add(new Cloud(N - 2, 1));

        while (M-- > 0) {
            st = new StringTokenizer(br.readLine());
            int d = Integer.parseInt(st.nextToken()) - 1;
            int s = Integer.parseInt(st.nextToken());

            stepOneTwo(d, s);

            stepThreeFour();

            stepFive();
        }

        int answer = 0;
        for (int[] i : grid) {
            for (int j : i) {
                answer += j;
            }
        }

        System.out.println(answer);
    }

    public static void stepOneTwo(int d, int s) {
        for (Cloud cloud : clouds) {
            // 구름이 di 방향으로 si칸 이동
            cloud.x = (N + cloud.x + dx[d] * (s % N)) % N;
            cloud.y = (N + cloud.y + dy[d] * (s % N)) % N;

            // 각 구름에서 비가 내려 구름이 있는 칸의 바구니에 저장된 물의 양이 1 증가
            grid[cloud.x][cloud.y]++;
        }
    }

    public static void stepThreeFour() {
        while (!clouds.isEmpty()) {
            // 구름이 모두 사라진다.
            Cloud cloud = clouds.poll();

            // 구름이 생기는 칸은 3에서 사라진 칸이 아니어야 한다.
            visit[cloud.x][cloud.y] = true;

            // 물복사버그 마법을 시전
            int cnt = 0;

            for (int k = 1; k <= 7; k += 2) { // 인접한 대각선 칸 검사
                int diagonalX = cloud.x + dx[k];
                int diagonalY = cloud.y + dy[k];

                // 경계를 넘어가는 칸은 대각선 방향으로 거리가 1인 칸이 아니다.
                if (diagonalX < 0 || diagonalY < 0 || diagonalX >= N || diagonalY >= N) continue;

                if (grid[diagonalX][diagonalY] > 0) {
                    cnt++;
                }
            }

            // 대각선 방향으로 거리가 1인 칸에 물이 있는 바구니의 수만큼 바구니의 물이 양이 증가
            grid[cloud.x][cloud.y] += cnt;
        }
    }

    public static void stepFive() {
        for (int i = 0; i < N; i++) {
            for (int j = 0; j < N; j++) {
                // 3에서 구름이 사라진 칸이 아니며 물의 양이 2 이상인 칸
                if (!visit[i][j] && grid[i][j] >= 2) {
                    // 구름 생성
                    clouds.add(new Cloud(i, j));
                    // 물의 양이 2 감소
                    grid[i][j] -= 2;
                }
            }
        }

        // 구름 사라진 칸 초기화
        visit = new boolean[N][N];
    }

    public static class Cloud {
        int x;
        int y;

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