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

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

문제

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

 

문제 분석

조건

N × N 격자에서 비구름을 M번 이동시킨다. 한 번의 이동 명령은 다음 단계로 이루어진다.

1. 모든 구름이 특정 방향으로 특정 칸만큼 이동한다. 격자는 경계가 연결되어 있다.
2. 구름이 있는 칸에 비가 내려 물의 양이 1 증가한다.
3. 물복사 마법이 시전된다. 비가 내렸던 칸은 대각선 방향에 물이 있는 칸의 수만큼 물의 양이 추가로 증가한다.
4. 이전에 구름이 있던 칸을 제외하고, 물의 양이 2 이상인 모든 칸에 새로운 구름이 생기고, 해당 칸의 물은 2만큼 줄어든다.

M번의 이동이 모두 끝난 후, 격자에 남아있는 물의 총 양을 구하는 문제이다.

풀이방법

단계별로 단순 순차적으로 구현하는 시뮬레이션 문제이다. 구름의 위치를 담은 `Queue`에서 모든 구름을 꺼내 이동키신 후, 물의 양을 증가시켰다. 이 좌표는 바로 다음 물 복사를 위해 `copyList`에 넣어주었다.

`copyList`에 저장된 비가 내렸던 칸에 물 복사를 하였고, 해당 칸의 물을 음수로 바꾸어 구름이 생성되면 안되는 칸을 표시했다.

그 후 `map`을 탐색하여 음수로 표시했던 부분은 양수로 바꾸고, 구름을 새로 `Queue`에 넣어주었다.

코드

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


public class Main {
    static class Cloud {
        int r, c;

        public Cloud(int r, int c) {
            this.r = r;
            this.c = c;
        }

        public void move(int d, int s, int N) {
            r = ((r + (dirs[d][0] * s)) % N + N) % N;
            c = ((c + (dirs[d][1] * s)) % N + N) % N;
        }
    }

    static int[][] dirs = {{0, -1}, {-1, -1}, {-1, 0}, {-1, 1}, {0, 1}, {1, 1}, {1, 0}, {1, -1}};
    static int[][] map;

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

        int N = Integer.parseInt(st.nextToken());
        int M = Integer.parseInt(st.nextToken());

        map = new int[N][N];
        for (int r = 0; r < N; r++) {
            st = new StringTokenizer(br.readLine());
            for (int c = 0; c < N; c++) {
                map[r][c] = Integer.parseInt(st.nextToken());
            }
        }

        Queue<Cloud> clouds = new ArrayDeque<>();
        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));
        for (int m = 0; m < M; m++) {
            st = new StringTokenizer(br.readLine());
            int d = Integer.parseInt(st.nextToken()) - 1;
            int s = Integer.parseInt(st.nextToken());
            List<int[]> copyList = new ArrayList<>();
            while (!clouds.isEmpty()) {
                Cloud cloud = clouds.poll();
                // 구름 이동
                cloud.move(d, s, N);
                // 물 증가
                map[cloud.r][cloud.c]++;
                // 복사마법 쓸 칸
                copyList.add(new int[]{cloud.r, cloud.c});
            }
            for (int[] pos : copyList) {
                waterCopy(pos[0], pos[1], N);
            }
            // 구름 생성. 구름이 사라진 칸이 아니여야함.
            for (int[] pos : copyList) {
                map[pos[0]][pos[1]] *= -1;  // 구름 없어진 칸 표시를 위해 음수로 바꿈
            }
            for (int r = 0; r < N; r++) {
                for (int c = 0; c < N; c++) {
                    if (map[r][c] < 0) {
                        map[r][c] *= -1;
                    } else if (map[r][c] >= 2) {
                        clouds.add(new Cloud(r, c));
                        map[r][c] -= 2;
                    }
                }
            }
        }

        // 정답
        int answer = 0;
        for (int r = 0; r < N; r++) {
            for (int c = 0; c < N; c++) {
                answer += map[r][c];
            }
        }
        System.out.println(answer);
    }

    private static void waterCopy(int r, int c, int N) {
        int d = 1;
        int count = 0;
        for (int i = 0; i < 4; i++) {
            int newR = r + dirs[d][0];
            int newC = c + dirs[d][1];
            if (newR < 0 || newC < 0 || newR >= N || newC >= N) {
                d += 2;
                continue;
            }
            if (map[newR][newC] > 0) {
                count++;
            }
            d += 2;
        }
        map[r][c] += count;
    }
}