[boj] 백준 21610 마법사 상어와 비바라기 (Java) - 시뮬레이션

[문제]

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

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

 

[풀이]

마법사 상어와 파이어볼 문제와 상당히 유사하다.

 

1. 초기 구름은 (N, 1), (N, 2), (N-1, 1), (N-1, 2) 에 존재한다. 구름 리스트를 만들어 구름을 세팅한다.

2. d방향으로 s만큼 구름을 이동한다. 이때 주의해야 할 점은 1-N 열과 행이 연결되어 있기 때문에 인덱스 오류가 나지 않도록 설정해야 한다. 위 문제와 똑같은데, d[i]*s%n 만큼 이동한 뒤, n을 초과하는 범위에 대해서는 -n, 0 이하의 범위에 대해서는 +n을 해주면 된다. 구름이 이동한 칸에는 비가 +1만큼 내리고, 이를 temp 에 추가해준다. 원래 구름이 있었던 칸에는 구름이 사라진 후, 다시 생기지 못하므로 visited 배열에 표시해준다.

3. 새로 비가 내린 칸에 대해서 대각선 4 방향에 대해 물이 있는 칸을 세주고 그만큼 물의 양을 더해준다.

4. 물의 양이 2이상이면서 이전에 구름이 사라진 칸이 아닌 칸에 구름이 새로 생기고 물의 양이 2씩 줄어든다. 

 

[코드]

 

package 시뮬레이션;

import java.io.*;
import java.util.*;

public class boj_21610_java {
    static int n, m;
    static int[][] A;
    static List<Cloud> clouds;
    static boolean[][] visited;
    static int[] dr = {0, -1, -1, -1, 0, 1, 1, 1}; // ←, ↖, ↑, ↗, →, ↘, ↓, ↙ 
    static int[] dc = {-1, -1, 0, 1, 1, 1, 0, -1};
    public static class Cloud{
        int r, c;
        Cloud(int r, int c){
            this.r = r; 
            this.c = c;
        }
    }
    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());

        A = new int[n+1][n+1]; //바구니의 물의 양
        
        clouds = new ArrayList<>();
        // (N, 1), (N, 2), (N-1, 1), (N-1, 2)에 비구름이 생긴다
        clouds.add(new Cloud(n, 1)); clouds.add(new Cloud(n, 2));
        clouds.add(new Cloud(n-1, 1)); clouds.add(new Cloud(n-1, 2));

        for(int i=1; i<=n; i++){
            st = new StringTokenizer(br.readLine());
            for(int j=1; j<=n; j++){
                A[i][j] = Integer.parseInt(st.nextToken());
            }
        }

        for(int i=0; i<m; i++){
            st = new StringTokenizer(br.readLine());
            int d = Integer.parseInt(st.nextToken()); //di방향으로 si만큼 이동
            int s = Integer.parseInt(st.nextToken());

            //모든 구름 이동
            moveCloud(d, s);

        } 

        //바구니에 들어있는 물의 양의 합
        int answer = 0;
        for(int i=1; i<=n; i++){
            for(int j=1; j<=n; j++){
                answer += A[i][j];
            }
        }

        System.out.println(answer);


    }

    public static void moveCloud(int d, int s){
        visited = new boolean[n+1][n+1];
        List<Cloud> temp = new ArrayList<>(); //물이 증가한 칸
        for(Cloud c:clouds){
            int nr = c.r + (dr[d-1]*s%n);
            int nc = c.c + (dc[d-1]*s%n);

            if(nr>n) nr -= n;
            if(nc>n) nc -= n;
            if(nr<=0) nr += n;
            if(nc<=0) nc += n;

            //비 내려서 +1 증가
            A[nr][nc]++;
            temp.add(new Cloud(nr, nc));
            visited[nr][nc] = true; //원래 구름이 있었던 칸 표시
        }

        //구름 사라짐, 대각선 방향으로 물이 있는 바구니 수만큼 r,c칸 물의 양 증가
        for(Cloud c:temp){
            int cnt = 0; //물이 있는 바구니 수

            for(int i=1; i<8; i+=2){ //1, 3, 5, 7 번째
                int nr = c.r + dr[i]; 
                int nc = c.c + dc[i];

                if(nr<1 || nc<1 || nr>n || nc>n) continue;

                if(A[nr][nc]>0) cnt++; //물이 들어있는 바구니의 개수 세기
            }

            //cnt만큼 물의 양 증가
            A[c.r][c.c] += cnt;
        }

        //물의 양이 2이상인 모든 칸에 구름이 생기고, 물의 양이 2씩 줄어든다
        clouds = new ArrayList<>();
        for(int i=1; i<=n; i++){
            for(int j=1; j<=n; j++){
                if(visited[i][j]) continue; //구름이 사라진 칸에서 구름이 생기지 않음
                if(A[i][j]>=2){
                    A[i][j] -= 2; //물의 양 줄어든다
                    clouds.add(new Cloud(i, j)); //구름이 생김
                }
            }
        }
    }
}