21610 - 마법사 상어와 비바라기

Byung Seon Kang·2022년 11월 24일
0

코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayDeque;
import java.util.Queue;
import java.util.StringTokenizer;

/**
 * @Author: kbs
 */
public class Main {

	//[0] : y좌표 [1] : x좌표
    static Queue<int[]> cloud = new ArrayDeque<>();
    static int N, M;
    static int[] dy = {0, -1, -1, -1, 0, 1, 1, 1};
    static int[] dx = {-1, -1, 0, 1, 1, 1, 0, -1};
    static int[][] arr;
    static boolean[][] visit;


    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());
        M = Integer.parseInt(st.nextToken());

        arr = new int[N + 1][N + 1];

        for (int i = 1; i <= N; i++) {
            st = new StringTokenizer(br.readLine());
            for (int j = 1; j <= N; j++) {
                arr[i][j] = Integer.parseInt(st.nextToken());
            }
        }
		
        //처음 비바라기 마법을 시전했을 때.
        cloud.add(new int[]{N, 1});
        cloud.add(new int[]{N - 1, 1});
        cloud.add(new int[]{N, 2});
        cloud.add(new int[]{N - 1, 2});

        for (int i = 1; i <= M; i++) {
            st = new StringTokenizer(br.readLine());
            int direction = Integer.parseInt(st.nextToken());
            int distance = Integer.parseInt(st.nextToken());

            useMagic(direction, distance);
            fillQueue();
        }

        System.out.println(allWaterSum());
    }

    private static int allWaterSum() {
        int sum = 0;
        for (int i = 1; i <= N; i++)
            for (int j = 1; j <= N; j++)
                sum += arr[i][j];

        return sum;
    }


    // 바구니에 저장된 물의 양이 2 이상인 모든 칸에 구름이 생기고, 물의 양이 2 줄어든다.
    private static void fillQueue() {
        for (int i = 1; i <= N; i++) {
            for (int j = 1; j <= N; j++) {
                if (arr[i][j] >= 2 && !visit[i][j]) {
                    cloud.add(new int[]{i, j});
                    arr[i][j] -= 2;
                }
            }
        }
    }

    private static void useMagic(int direction, int distance) {
        int size = cloud.size();

        // 모든 구름이 di 방향으로 si칸 이동한다.
        // 각 구름에서 비가 내려 구름이 있는 칸의 바구니에 저장된 물의 양이 1 증가한다.
        for (int i = 1; i <= size; i++) {
            int[] current = cloud.poll();
            int pointY = current[0] + dy[direction - 1] * (distance % N);
            int pointX = current[1] + dx[direction - 1] * (distance % N);

            pointY = changePoint(pointY);
            pointX = changePoint(pointX);

            arr[pointY][pointX] += 1;
            cloud.add(new int[]{pointY, pointX});
        }

        // 2에서 물이 증가한 칸 (r, c)에 물복사버그 마법을 시전한다.
        visit = new boolean[N + 1][N + 1];

        while (!cloud.isEmpty()) {
            int[] current = cloud.poll();
            visit[current[0]][current[1]] = true;

            for (int i = 1; i <= 7; i += 2) {
                int nextY = current[0] + dy[i];
                int nextX = current[1] + dx[i];

                // 이때는 이동과 다르게 경계를 넘어가는 칸은 대각선 방향으로 거리가 1인 칸이 아니다.
                if (nextY > N || nextY < 1 || nextX > N || nextX < 1) continue;
                ;
                if (arr[nextY][nextX] >= 1) arr[current[0]][current[1]] += 1;
            }
        }
    }

    private static int changePoint(int point) {
        if (point > N) {
            point = point - N;
        } else if (point < 1) {
            point = point + N;
        }

        return point;
    }
}
  • 조건이 복잡한 구현문제.
  • 구름을 추가할 때 이전에 구름이 사라졌던 위치를 visit배열로 기록해두고 처리했다.
  • 큐를 사용해 구름의 위치들을 저장했다.
profile
왜 필요한지 질문하기

0개의 댓글