[백준]21610: 마법사 상어와 비바라기(java)

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

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

문제

마법사 상어는 파이어볼, 토네이도, 파이어스톰, 물복사버그 마법을 할 수 있다. 오늘 새로 배운 마법은 비바라기이다. 비바라기를 시전하면 하늘에 비구름을 만들 수 있다. 오늘은 비바라기를 크기가 N×N인 격자에서 연습하려고 한다. 격자의 각 칸에는 바구니가 하나 있고, 바구니는 칸 전체를 차지한다. 바구니에 저장할 수 있는 물의 양에는 제한이 없다. (r, c)는 격자의 r행 c열에 있는 바구니를 의미하고, A[r][c]는 (r, c)에 있는 바구니에 저장되어 있는 물의 양을 의미한다.

격자의 가장 왼쪽 윗 칸은 (1, 1)이고, 가장 오른쪽 아랫 칸은 (N, N)이다. 마법사 상어는 연습을 위해 1번 행과 N번 행을 연결했고, 1번 열과 N번 열도 연결했다. 즉, N번 행의 아래에는 1번 행이, 1번 행의 위에는 N번 행이 있고, 1번 열의 왼쪽에는 N번 열이, N번 열의 오른쪽에는 1번 열이 있다.

비바라기를 시전하면 (N, 1), (N, 2), (N-1, 1), (N-1, 2)에 비구름이 생긴다. 구름은 칸 전체를 차지한다. 이제 구름에 이동을 M번 명령하려고 한다. i번째 이동 명령은 방향 di과 거리 si로 이루어져 있다. 방향은 총 8개의 방향이 있으며, 8개의 정수로 표현한다. 1부터 순서대로 ←, ↖, ↑, ↗, →, ↘, ↓, ↙ 이다. 이동을 명령하면 다음이 순서대로 진행된다.

1. 모든 구름이 di 방향으로 si칸 이동한다.
2. 각 구름에서 비가 내려 구름이 있는 칸의 바구니에 저장된 물의 양이 1 증가한다.
3. 구름이 모두 사라진다.
4. 2에서 물이 증가한 칸 (r, c)에 물복사버그 마법을 시전한다. 물복사버그 마법을 사용하면, 대각선 방향으로 거리가 1인 칸에 물이 있는 바구니의 수만큼 (r, c)에 있는 바구니의 물이 양이 증가한다.
   • 이때는 이동과 다르게 경계를 넘어가는 칸은 대각선 방향으로 거리가 1인 칸이 아니다.
   • 예를 들어, (N, 2)에서 인접한 대각선 칸은 (N-1, 1), (N-1, 3)이고, (N, N)에서 인접한 대각선 칸은 (N-1, N-1)뿐이다.
5. 바구니에 저장된 물의 양이 2 이상인 모든 칸에 구름이 생기고, 물의 양이 2 줄어든다. 이때 구름이 생기는 칸은 3에서 구름이 사라진 칸이 아니어야 한다.

M번의 이동이 모두 끝난 후 바구니에 들어있는 물의 양의 합을 구해보자.

입력

첫째 줄에 N, M이 주어진다.

둘째 줄부터 N개의 줄에는 N개의 정수가 주어진다. r번째 행의 c번째 정수는 A[r][c]를 의미한다.

다음 M개의 줄에는 이동의 정보 di, si가 순서대로 한 줄에 하나씩 주어진다.

출력

첫째 줄에 M번의 이동이 모두 끝난 후 바구니에 들어있는 물의 양의 합을 출력한다.

제한

• 2 ≤ N ≤ 50
• 1 ≤ M ≤ 100
• 0 ≤ A[r][c] ≤ 100
• 1 ≤ di ≤ 8
• 1 ≤ si ≤ 50

예제 입력 1 복사

5 4
0 0 1 0 2
2 3 2 1 0
4 3 2 9 0
1 0 2 9 0
8 8 2 1 0
1 3
3 4
8 1
4 8

예제 출력 1 복사

77

구름이 있는 칸은 빨간색으로 표시했고, 물이 증가한 칸은 초록색으로 표시했다.

0	0	1	0	2
2	3	2	1	0
4	3	2	9	0
1	0	2	9	0
8	8	2	1	0

첫 번째 이동은 구름이 1번 방향(←)으로 3칸 이동해야 한다. 구름이 이동한 후는 다음과 같다.

0	0	1	0	2
2	3	2	1	0
4	3	2	9	0
1	0	2	9	0
8	8	2	1	0

구름이 있는 칸에 비가 1씩 내리고, 구름은 사라진다.

0	0	1	0	2
2	3	2	1	0
4	3	2	9	0
1	0	3	10	0
8	8	3	2	0

(4, 3)은 대각선 4개의 방향 모두에 물이 있다. 따라서, 물의 양이 4 증가해 7이 된다. (4, 4)는 대각선 2개의 방향(↖, ↙)에 물이 있다. 물의 양은 2 증가하고, 12가 된다. (5, 3)은 대각선으로 거리가 1인 칸이 2개(↖, ↗)있고, 이 중에서 1개(↗)만 물이 있다. 따라서, 물의 양은 3에서 4로 변한다. (5, 4)도 방향 1개(↖)만 물이 있기 때문에, 물의 양이 3이 된다.

0	0	1	0	2
2	3	2	1	0
4	3	2	9	0
1	0	7	12	0
8	8	4	3	0

이제 구름이 있었던 칸을 제외한 나머지 칸 중에서 물의 양이 2 이상인 칸에 구름이 생긴다. 구름이 생기면 물의 양이 2만큼 줄어든다.

0	0	1	0	0
0	1	0	1	0
2	1	0	7	0
1	0	7	12	0
6	6	4	3	0

두 번째 이동이 끝난 후의 상태는 다음과 같다.

2	1	1	0	0
0	1	0	1	2
5	4	5	5	0
4	5	12	15	0
4	4	2	1	0

다음은 세 번째 이동이 끝난 후의 상태이다.

4	2	4	0	2
0	1	0	1	0
3	2	3	3	0
2	3	17	13	0
2	2	0	1	0

모든 이동이 끝난 최종 상태는 다음과 같다.

2	4	2	2	4
3	1	0	5	3
1	0	1	1	0
0	1	22	11	0
4	5	0	3	2

---

풀이

시뮬레이션 문제였다. 문제에서 요구하는바를 단계별로 설명해보겠다.

1. 모든 구름이 d 방향으로 s칸 이동한다.

- 이 때 구름은 배열을 넘어가도 반대로 나올 수 있다.

- 이때 현재 구름이 있는곳을 visited를 통해 체크해주었다.

private static void moveCloud(int idx) {
    int d = cloudMove[idx][0];
    // N 번은 제자리로 돌아옴
    int mCnt = cloudMove[idx][1] % N;
    for(Point p: cloud) {
        int nx = p.x;
        int ny = p.y;
        for(int i=0; i<mCnt; i++) {
            nx+=dist[d][0];
            ny+=dist[d][1];
            if(nx > N) nx = 1;
            else if(nx < 1) nx = N;
            if(ny > N) ny = 1;
            else if(ny < 1) ny = N;
        }
        p.x = nx;
        p.y = ny;
        visited[p.x][p.y] = true;
    }
}

2. 구름이 있는 곳 바구니의 물 양을 1 증가시킨다.

private static void getWater() {
    for(Point p: cloud) {
        map[p.x][p.y]++;
    }
}

3. 현재 구름이있는 바구니의 대각선에 물이 있다면 물의 양을 1 증가시킨다.

private static void increaseWater() {
    for(Point p: cloud) {
        for(int i=2; i<=8; i+=2) {
            int nx = p.x+dist[i][0];
            int ny = p.y+dist[i][1];
            // 범위 초과하거나 대각선에 물이 없다면 continue
            if(!isIn(nx, ny) || map[nx][ny] <= 0) continue;
            map[p.x][p.y]++;
        }
    }
}

4. 구름을 삭제한다.

private static void deleteCloud() {
    cloud.clear();
}

5. 구름을 삭제한 곳을 제외하고 물의 양이 2 이상있는 곳에 구름을 생성하고 물의 양이 2 줄어든다.

private static void setCloud() {
    for(int i=1; i<=N; i++) {
        for(int j=1; j<=N; j++) {
            if(map[i][j] < 2 || visited[i][j]) continue;
            cloud.add(new Point(i, j));
            map[i][j]-=2;
        }
    }
}

6. 1~5를 총 M번 반복한 후 최종 물의 양을 구한다.

private static void getSumWater() {
    int sum = 0;
    for(int i=1; i<=N; i++) {
        for(int j=1; j<=N; j++) {
            sum+=map[i][j];
        }
    }

    System.out.println(sum);
}

전체코드

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.LinkedList;
import java.util.StringTokenizer;

public class BJ_G5_21610_마법사상어와비바라기 {
    static class Point {
        int x;
        int y;

        @Override
        public String toString() {
            return "Point{" +
                    "x=" + x +
                    ", y=" + y +
                    '}';
        }

        Point(int x, int y) {
            this.x = x;
            this.y = y;
        }
    }
    static int N, M;
    static int[][] map;
    static int[][] cloudMove;
    static boolean[][] visited;
    static LinkedList<Point> cloud = new LinkedList<>();
    //x, ←, ↖, ↑, ↗, →, ↘, ↓, ↙
    static int dist[][] = {{}, {0, -1}, {-1, -1}, {-1, 0}, {-1, 1}, {0, 1}, {1, 1}, {1, 0}, {1, -1}};
    public static void main(String[] args) throws Exception{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        N = Integer.parseInt(st.nextToken());
        M = Integer.parseInt(st.nextToken());
        map = new int[N+1][N+1];
        cloudMove = new int[M][2];
        for(int i=1; i<=N; i++) {
            st = new StringTokenizer(br.readLine());
            for(int j=1; j<=N; j++) {
                map[i][j] = Integer.parseInt(st.nextToken());
            }
        }

        for(int i=0; i<M; i++) {
            st = new StringTokenizer(br.readLine());
            int dist = Integer.parseInt(st.nextToken());
            int moveCnt = Integer.parseInt(st.nextToken());

            cloudMove[i][0] = dist;
            cloudMove[i][1] = moveCnt;
        }
        //초기 구름 세팅
        cloud.add(new Point(N, 1));
        cloud.add(new Point(N, 2));
        cloud.add(new Point(N-1, 1));
        cloud.add(new Point(N-1, 2));

        goSimulation();
    }

    private static void goSimulation() {
        for(int i=0; i<M; i++) {
            //1. 모든 구름이 d방향으로 s칸 이동한다.
            visited = new boolean[N+1][N+1];
            moveCloud(i);
            getWater();
            increaseWater();
            deleteCloud();
            setCloud();
        }
        getSumWater();
    }

    private static void moveCloud(int idx) {
        int d = cloudMove[idx][0];
        // N 번은 제자리로 돌아옴
        int mCnt = cloudMove[idx][1] % N;
        for(Point p: cloud) {
            int nx = p.x;
            int ny = p.y;
            for(int i=0; i<mCnt; i++) {
                nx+=dist[d][0];
                ny+=dist[d][1];
                if(nx > N) nx = 1;
                else if(nx < 1) nx = N;
                if(ny > N) ny = 1;
                else if(ny < 1) ny = N;
            }
            p.x = nx;
            p.y = ny;
            visited[p.x][p.y] = true;
        }
    }

    private static void getWater() {
        for(Point p: cloud) {
            map[p.x][p.y]++;
        }
    }

    private static void increaseWater() {
        for(Point p: cloud) {
            for(int i=2; i<=8; i+=2) {
                int nx = p.x+dist[i][0];
                int ny = p.y+dist[i][1];
                // 범위 초과하거나 대각선에 물이 없다면 continue
                if(!isIn(nx, ny) || map[nx][ny] <= 0) continue;
                map[p.x][p.y]++;
            }
        }
    }

    private static void deleteCloud() {
        cloud.clear();
    }

    private static void setCloud() {
        for(int i=1; i<=N; i++) {
            for(int j=1; j<=N; j++) {
                if(map[i][j] < 2 || visited[i][j]) continue;
                cloud.add(new Point(i, j));
                map[i][j]-=2;
            }
        }
    }

    private static void getSumWater() {
        int sum = 0;
        for(int i=1; i<=N; i++) {
            for(int j=1; j<=N; j++) {
                sum+=map[i][j];
            }
        }

        System.out.println(sum);
    }

    private static boolean isIn(int x, int y) {
        return 0<x && x<=N && 0<y && y<=N;
    }
}
/*
A[r][c] = (r, c) 바구니의 물의 양
좌상단 : (1,1) 우하단 : (N, N)

1에서 위로가면 N
N에서 아래로가면 1로 갈 수 있음

비바라기 시전하면 (N, 1), (N, 2), (N-1, 1), (N-1, 2)에 비구름이 생김
방향은 1부터 순서대로 ←, ↖, ↑, ↗, →, ↘, ↓, ↙

1. 모든 구름이 d방향으로 s칸 이동
2. 구름이 있는 곳 바구니 물 양 1 증가
3. 구름 모두 사라짐
4. 물이 1 증가한 바구니는 대각 방향에 물이 있다면 그 수만큼 물이 증가함. (이땐 위 아래로 넘어갈 수 없음)
5. 구름이 원래 있었던 곳을 제외한 곳에 물이 2 이상 있는 곳에 구름이 생긴 후 모두 물이 2 줄어든다.
 */